שאלת מיונים!

[GuestOfHonor]

שאלת מיונים!

נניח שיש לי n שלמים שערכם הוא בין 0 ל n²-1. איך אני ממיין אותם ב O ?

 

[vinney]

מיון דליים?

 

[shirbi]

איך? זה יקח O של N בריבוע, לא?

כלומר, המעבר על המערך לוקח O של N, אבל אח"כ צריך לעבור על כל ה"דליים" שאומנם רובם ריקים, אבל עדין צריך לעבור עליהם, וזה יקח כמספר ה"דליים" כלומר O של N בריבוע.

 

[vinney]

לא מדויק, תראה את המשך הדיון

 

[shirbi]

ואללה. עכשיו שנזכרתי מה זה

RADIX SORT, אז זה בהחלט נשמע לי אפשרי.

 

[sf8f]

אתה הולך לך

cs.huji.ac.il/~dast ויש שם רמז עבה

 

[ron369]

ההודעה של ויני אינה רמז עבה יותר?

(איך אפשר לעשות רמז עבה מהפתרון עצמו?

)

 

[vinney]

זה לא ממש הפתרון../images/Emo13.gif

רק מיון דליים לא יספיק פה כמובן, כי אתה לא יודע שום דבר על פיזור הנתונים, אבל כחלק מRADIX זה יעבוד מצוין.

 

[ron369]

אה...

אז כנראה רק עבור אדם חצי ישן זה הפתרון ממש

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

 

[vinney]

הא? עוד לא התעוררת נראה לי...../images/Emo6.gif

 

[ron369]

גם נכון, אבל יש בהודעה שלי הגיון

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

 

[vinney]

לא מבין...

אם החסם שלך הוא 2 בחזקת N, אתה לא יכול לעשות את זה?

 

[ron369]

אתה יכול?

בינתיים, לא רואה איך ב-O(N).

 

[vinney]

לודע, לא חשבתי על זה ../images/Emo13.gif

אבל כנראה שלא, כי הטריק הוא שהייצוג של כל ספרה הוא לינארי בN.

 

[GuestOfHonor]

הפיתרון, למי שזה מעניין אותו

מסתכלים על כל אחד מהמספרים בקלט כבן 2 ספרות. כל אחת בבסיס n (תגידו שזה לא מופרע... ). כל מספר בגודל 0..n²-1 אפשר באמת ליצג בצורה כזאת של מספר דו-ספרתי. כעת, מפעילים Radix Sort (פרק 8 בקורמן) , וזמן הריצה הוא לינארי. (2(n+n))O=O