אלגוריתם יעיל לחלוקת מערך לקבוצות

[Abod היחיד]

אלגוריתם יעיל לחלוקת מערך לקבוצות

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

 

[yuvalmadar]

בקשת הבהרה

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

 

[Abod היחיד]

הבהרות:

a הקבוצות צריכות להיות בעלות גודל שווה עד כדי הבדל של 1 בקבוצות האחרונות. בכל קבוצה יהיו: ערך_עליון(n/a) ערכים או המספר הזה פחות 1. הקבוצות ממויינות זו ביחס לזו.

 

[IP yuval]

תחשוב Quicksort

 

[Abod היחיד]

חשבתי.. לא מתאים לסיבוכיות

 

[IP yuval]

קרא את זה (את הכל):

http://en.wikipedia.org/wiki/Quicksort ותחשוב שוב על אלגוריתם שפותר את הבעיה.

 

[Abod היחיד]

אני מכיר את האלגוריתם הזה

וכבר הגעתי לואריאציה כלשהי שפותרת את הבעיה אבל לא בסיבוכיות המתאימה...

 

[IP yuval]

למה? למה הגעת?

 

[Abod היחיד]

הנה הרעיון

ב-O ddd אני יכול למצוא את האיבר ה-i במערך ולעשות Partiotion לפיו. כלומר ב-O ddd אני יכול להפריד את הקבוצה הראשונה משאר המערך. נשאר לי מערך עם n-[n/a] ddd ערכים שאני צריך להפריד ל-a-1 קבוצות... הסיבוכיות יוצאת n*a ואני צריך n*log a

 

[IP yuval]

תחשוב מאיפה quicksort מקבל את

הlog שלו.

 

[Abod היחיד]

מספר הערות

1. ה-QuickSort פועל ב O(n*log n) ddd זמן ממוצע(!) ובמקרה הגרוע הוא O(n^2) ddd. 2. אולי שכחתי לכתוב, אבל הדרישת סיבוכיות לאלגוריתם שלי היא למקרה גרוע ולא ממוצע. 3. QuickSort מקבל את הלוג n שלו מעצם חלוקת המערך ל-2 מערכים שקטנים ממנו בחצי וטיפול בכל אחד מהם בנפרד. אני לא רואה איך זה עוזר לי לאלגוריתם שלי... אולי יש לך רעיון ספציפי יותר?

 

[IP yuval]

1. לא הקשבת לעצה שלי.

2. זה היה צפוי. 3. למה שגם אתה לא תעבוד ככה?

 

[Abod היחיד]

אני מנסה...

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

 

[IP yuval]

טוב,

אם היית קורא את הערך בויקיפדיה, היית מגלה שquicksort יכול לרוץ גם בnlogn במקרה הגרוע כאשר חוצים לפי החציון. פתרון אפשרי לבעיה שלך היא פשוט לבצע את החלוקה מספר מוגבל של פעמים ששווה ללוג של a. עכשיו תחשוב לבד מה קורה כאשר n וa הם לא חזקות יפות של 2...

 

[Abod היחיד]

לא הבנתי מה אתה מתכוון

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

 

[IP yuval]

אם a =2 אז אתה עושה חלוקה אחת

של המערך (partition), וזמן הריצה הוא n*log2(2) ddd. אם a =4, אז אתה מחלק את המערך ל2 ואז כל חלק אתה מחלק ל2. אם a = 8 אתה מחלק את המערך ל4 ומחלק שוב כל קבוצה ל2.

 

[Abod היחיד]

עכשיו מובן, תודה רבה!

 

[Abod היחיד]

בעיה קטנה שעליתי עליה...

האלגוריתם שאני מכיר למציאת האיבר ה-i במערך מתבצעת ב-O ddd בממוצע... ולא O ddd במקרה הגרוע. יש אלגוריתם שעושה את זה גם במקרה הגרוע?

 

[IP yuval]

שוב,

http://www.tapuz.co.il/tapuzforum/main/Viewmsg.asp?forum=1428&msgid=69705847

 

[Abod היחיד]

אבל לבעיה הזאת כבר בטוח יש פתרון

אתה יודע אולי שם של אלגוריתם? או אפילו לינק לאלגוריתם כזה? גם אלגוריתם למציאת חציון ב-O worst-case יהיה טוב לי, להכליל משם בטח לא יהיה קשה במיוחד.