טבלת גיבוב

[n0b0dy]

טבלת גיבוב

נתון לי מערך A בגודל n המכיל שורש n ערכים שונים מתוך התחום [1...k] ו k קבוע. אני צריך להציע מבנה נתונים (או כמה מבני נתונים) למיון המערך בסיבוכיות של O(N) במקרה הממוצע. בהתחלה חשבתי על מיון מניה , אבל לא נתון לי שהערכים שלמים. חשבתי גם על מיון דלי , אבל לא נתון לי פיזור אחיד

נראה לי שמיונים ליניארים לא יעזרו לי פה, וחשבתי שאולי אפשר לעשות את זה באמצעות טבלת גיבוב, רק שלא עולה לי שום רעיון איך ליישם את זה... אשמח לעצות לפיתרון, תודה!

 

[vinney]

מה דרשו ממך?

מיון דלי או מניה זה אלגוריתם, טבלת גיבוב זה מבנה נתונים. אם שאלו אותך "איזה מבנה נתונים יאפשר לבצע מיון לינארי", כנראה שהתשובה היא באמת טבלת גיבוב, אם השאלה היא "תציע אלגוריתם מיון לינארי", אז טבלת גיבוב זה יעזור לך, אבל זאת לא תשובה.

 

[vinney]

(במאמר מוסגר, אני חייב לציין)

שכנראה שלא משנה מה אתה חושב שביקשו ממך, בסוף תצטרך להציע אלגוריתם. למה? כי אם תגיד "מבנה נתונים X מאפשר מיון לינארי", תצטרך גם להוכיח את זה, דהיינו להראות מיון שממין לינארית, ומשתמש במבנה הנתונים שהצעת.

 

[n0b0dy]

מה שדרשו

דרשו בשאלה : " הצע מבנה נתונים ואלגוריתם המשתמש בו" בכל מקרה אצטרך להסביר בפירוט את מבנה הנתונים שבחרתי ולהוכיח שהסיבוכיות שלו היא O במקרה הממוצע.. אתה חושב שטבלת גיבוב תתאים פה? כי אני לא מצליח למצוא כיוון במיונים ליניארים, תמיד יש נתון שחסר לי ואני לא יכול להניח סתם כך תודה

 

[vinney]

המם...

אתה לא בהכרח צריך טבלת גיבוב. רשימה מקושרת זה גם סוג של מבנה נתונים, למשל.

 

[n0b0dy]

המם...

לפי מה שאני יודע (ואשמח לתיקון אם אני טועה) מיון רשימה יקח לי O(nlgn) MergeSort.... אני מנסה לחשוב איך הנתון שקיימים שורש n ערכים שונים עוזר לי, כי אף פעם לא "מנדבים" נתונים

חשבתי על טבלה בגודל שורש n , שבכל תא יהיה ערך אחר (כמ"ס הערכים השונים שנתון לי), ואם מופיע ערך זהה לערך שכבר נמצא בטבלה אז לפתור את זה באמצעות שרשור (רשימה מקושרת). אבל הרעיון נראה לי בוסרי מידי, ואין לי רעיון איך לכתוב את פונקצית הגיבוב שתכניס אותם בסדר ממויין לטבלה...

 

[vinney]

כמה זה שורש N בריבוע?

 

[n0b0dy]

N , איך זה קשור אבל..?

 

[vinney]

אם המערך שלך הוא בגודל

שורש N , והסיבוכיות הנדרשת ממך היא N, אז אתה יכול לעשות מיון בועות, ולעמוד בתנאי.

 

[n0b0dy]

כן אבל

חשבתי על מערך בגודל שורש n בהנחה שאני אשרשר ערכים זהים לאותו תא (מכל תא במערך יהיה מצביע לרשימה מקושרת שתכיל ערכים זהים), וכך לפתור בעצם את פיתרון ההתנגשות (בהנחה שמדובר בטבלת גיבוב), ולעמוד בסיבוכיות הנדרשת. המערך המקורי שלי הוא בגודל n , ונראה לי שאם אשתמש במיון בועות אני לא אוכל להניח מערך בגודל שורש n כי אחרי הכל יש לי n איברים... או שאני טועה?

 

[vinney]

למה אתה צריך לשרשר ערכים

זהים? אתה רק צריך לדעת כמה כאלה יש לך, זה הכל. לא הבנתי עדיין למה אתה צריך טבלת גיבוב... מערך זה בהחלט מספיק (יש לך כמה אופציות, אתה יכול להשתמש בזה שאתה יודע שיש לך רק שורש N ערכים, אתה יכול להשתמש בזה שיש לך K אפשרויות שונות לערך, וכד').

 

[n0b0dy]

חשבתי

על טבלת גיבוב כי אני נדרש לבצע מיון בזמן לינארי, את המיונים הליניארים פסלתי מחוסר נתונים, לכן חשבתי על טבלת גיבוב ומכיוון שעדיין לא הצלחתי לפסול את האופציה (אבל גם לא לוודא שהיא מתאימה) אני ממשיך לחקור אותה. יכול להיות שמערך מספיק כאן, אני פשוט לא רואה איך...כלומר איך אני יכול לבצע מה שדרשו ממני רק באמצעות מערך ? (איך הנתונים עוזרים לי פה ע"מ לבצע את זה בסיבוכיות שדרשו ממני?)

 

[vinney]

שכח מטבלת גיבוב!

אם זה לא היה לך ברור מכל השרשור הארוך הזה - אתה לא צריך אותה. אתה צריך מערך. תמשיך להתקדם מפה.

 

[n0b0dy]

אני עדיין לא רואה איך

אני יכול לעמוד בסיבוכיות הנדרשת רק באמצעות מערך... אני אצטרך להעביר כל ערך פעם אחת למערך עזר בגודל שורש N לבצע מיון בועות על מערך העזר (שזה באמת יקח O, ולסרוק שוב את המערך ע"מ לספור כמה פעמים כל ערך מופיע לי, ולהעביר אותם למערך עזר נוסף בגודל N - שהוא יהיה המערך הממוין. המעברים על המערך כל פעם יקחו לי O(n^2)...

 

[vinney]

איך הגעת לזה?

המעבר על המערך הוא לינארי, אתה בונה את מערך העזר בO של n, ממיין אותו בגג O של n (מיון מיזוג יעשה את זה בפחות), ומעביר חזרה בO של N שוב. הטריק הוא שאמרו לך שטווח הערכים הוא ידוע מראש וקבוע. אתה לא צריך לחפש את הערך במערך כדי לדעת שהוא כבר שם, אתה פשוט צריך עוד מערך עזר שיגיד לך כמה פעמים כל ערך מופיע.

 

[n0b0dy]

אולי

לא הסברתי את השאלה נכון, או שלא הבנתי את הטריק... טווח הערכים הוא בין [1...k] נניח יכול להיות מצב ש n=4, ואז יש לי במערך 2 ערכים שונים מתוך הטווח (סתם דוגמא) : [1...1000] (k = 1000) במקרה כזה אני חייב לחפש את הערך במערך כדי לדעת שהוא כבר שם, כי אני לא יודע איזה ערכים מתוך הטווח נמצאים שם... לא הסברתי את השאלה נכון? לא הבנתי את הטריק? אני מבולבל..

 

[vinney]

לא הבנת את הטריק

היופי במערך הוא שהשליפה היא בO של 1. אתה לא צריך לחפש שום דבר, אתה ניגש לפי אינדקס. תחשוב מה האינדקס.

 

[n0b0dy]

Vinney

אתה יכול להסביר בפירוט את הרעיון שלך בשימוש במערך? זה פשוט עוד לא מסתדר לי, איך זה עומד בסיבוכיות הנדרשת, ואני תקוע עם השאלה הזאת לעבודה שאני חייב להגיש מחר... תודה