שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2010 - סיבוכיות

נתבונן בשיטה הבאה למיון קבוצה $A_0$ של $n$ מספרים שונים: נחלק את $A_0$ ל $n$ קבוצות זרות בגודל $1$ כל אחת. אח"כ נבחר בכל פעם את האיבר הקטן ביותר מתוך אלה שעוד לא נבחרו ע"י שנמצא (בזמן לינארי) את האיבר הקטן ביותר בתוך כל אחת מ $n$ הקבוצות (נקרא לקבוצת הקטנים האלה $A_1$), ואז נמצא את האיבר הקטן ביותר ב-$A_1$. א( כמה זמן לוקח מציאת האיבר הקטן ביותר? והשני? הסכם/י: מה הסיבוכיות של שיטת מיון זו? ב( האם יעזור אם, במקום לחזור ולחפש שוב ושוב את האיבר הקטן בכל קבוצה, נמיין את הקבוצות מיד בהתחלה? ג( כדי לשפר, נחלק את $A_0$ ל $n^{2/3}$ קבוצות בגודל $n^{1/3}$ כל אחת. נקבל קבוצה $A_1$ בגודל $n^{2/3}$ ולכן גם אותה נחלק ל $n^{1/3}$ קבוצות בגודל $n^{1/3}$. נקרא לקבוצת האיברים המינימליים בשם $A_2$. כמה זמן לוקח מציאת האיבר הקטן ביותר? והשני? הסכם/י: מה הסיבוכיות של שיטת מיון זו? ד( תאר/י בקצרה הכללה של השיטה של א) ($1$ רמה נוספת אחת) ו ג) ($2$ רמות נוספות) ל $k$ רמות נוספות. מה תהיה הסיבוכיות? ה( מהו הערך הגדול ביותר של $k$ שהוא אפשרי ב ג)? (רמז: חייבים להיות לפחות $2$ איברים בכל קבוצה בחלוקה). איזה שיטת מיון מתקבלת עבור $k$ זה? הסבר/י.

רמז: כדי לחשב את הסיבוכיות הכוללת, חשבו בנפרד את עלות מציאת האיבר הראשון (בניית המבנה) ואת עלות מציאת כל אחד מ-$n-1$ האיברים הבאים (עדכון המבנה).

פתרון: א. **מציאת האיבר הקטן ביותר:** התהליך כולל שני שלבים: 1. יצירת קבוצה $A_1$ מהאיברים המינימליים של $n$ הקבוצות בגודל 1. מכיוון שהקבוצות בגודל 1, שלב זה לוקח $O(n)$. 2. מציאת המינימום בקבוצה $A_1$ (שהיא למעשה $A_0$) על-ידי סריקה לינארית, שלוקחת $O(n)$. סך הכל, מציאת האיבר הראשון לוקחת $O(n)$. **מציאת האיבר השני:** לאחר שהאיבר הקטן ביותר נמצא והוסר, אנו חוזרים על התהליך עבור $n-1$ האיברים הנותרים. יש עדיין $n$ קבוצות, אחת מהן ריקה. יצירת קבוצת המינימליים $A_1'$ לוקחת שוב $O(n)$, ומציאת המינימום בה לוקחת $O(n-1)$. סך הכל, גם מציאת האיבר השני לוקחת $O(n)$. **סיבוכיות המיון:** כדי למיין את כל המערך, יש לחזור על תהליך מציאת האיבר המינימלי הבא $n$ פעמים. מכיוון שכל איטרציה עולה $O(n)$, **הסיבוכיות** הכוללת של שיטת המיון היא $n \cdot O(n) = O(n^2)$. זוהי למעשה גרסה של **מיון בחירה (Selection Sort)**. ב. במקרה זה, הקבוצות הראשוניות הן בגודל 1, ולכן הן כבר "ממוינות". ביצוע פעולת מיון על קבוצה בגודל 1 הוא פעולה של $O(1)$. לכן, מיון כל $n$ הקבוצות מראש ייקח $O(n)$ זמן. שלב זה אינו משנה את צוואר הבקבוק של האלגוריתם, שהוא החיפוש החוזר ונשנה של המינימום מבין $O(n)$ איברים בכל איטרציה. לכן, **הדבר לא יעזור** והסיבוכיות תישאר $O(n^2)$. ג. בשיטה המשופרת, אנו בונים **מבנה היררכי** של שני שלבים. **מציאת האיבר הקטן ביותר (עלות הקמה):** 1. מחלקים את $A_0$ (גודל $n$) ל-$n^{2/3}$ קבוצות בגודל $n^{1/3}$. מציאת המינימום בכל קבוצה כזו עולה $O(n^{1/3})$. סך הכל לשלב זה: $n^{2/3} \cdot O(n^{1/3}) = O(n)$. התוצאה היא קבוצה $A_1$ בגודל $n^{2/3}$. 2. מחלקים את $A_1$ ל-$n^{1/3}$ קבוצות בגודל $n^{1/3}$. מציאת המינימום בכל קבוצה עולה $O(n^{1/3})$. סך הכל לשלב זה: $n^{1/3} \cdot O(n^{1/3}) = O(n^{2/3})$. התוצאה היא קבוצה $A_2$ בגודל $n^{1/3}$. 3. מוצאים את המינימום ב-$A_2$ בסריקה לינארית בעלות $O(n^{1/3})$. העלות הכוללת למציאת האיבר הראשון היא סכום העלויות: $O(n) + O(n^{2/3}) + O(n^{1/3}) = O(n)$. **מציאת האיבר השני (עלות עדכון):** לאחר שמצאנו את המינימום הכולל והסרנו אותו, איננו צריכים לבנות הכל מחדש. נניח שהמינימום הגיע מקבוצה $S$ ברמה הנמוכה ביותר. 1. נמצא את המינימום החדש בקבוצה $S$ (שגודלה כעת $n^{1/3}-1$). עלות: $O(n^{1/3})$. 2. מינימום חדש זה מחליף את המינימום הקודם בקבוצה $A_1$. שינוי זה משפיע רק על קבוצה אחת ברמה הבאה. נמצא את המינימום החדש בקבוצה זו. עלות: $O(n^{1/3})$. 3. שינוי זה מתגלגל הלאה לקבוצה $A_2$. כעת נמצא את המינימום החדש ב-$A_2$. עלות: $O(n^{1/3})$. העלות הכוללת למציאת האיבר השני היא $O(n^{1/3})$. **סיבוכיות המיון:** עלות ההקמה היא $O(n)$, ולאחר מכן יש $n-1$ פעולות "הוצאת מינימום" שכל אחת עולה $O(n^{1/3})$. הסיבוכיות הכוללת היא $O(n) + (n-1) \cdot O(n^{1/3}) = O(n + n^{4/3}) = O(n^{4/3})$. ד. **הכללה ל-$k$ רמות:** נכליל את השיטה כך שבמקום 2 רמות היררכיה, יהיו $k$ רמות. נחלק את הקבוצה בכל רמה לתתי-קבוצות בגודל $b$. כדי שהמבנה יהיה סימטרי, נבחר את גודל תת-הקבוצה $b$ כך שיתקיים $n = b^{k+1}$, כלומר $b = n^{1/(k+1)}$. - **עלות הקמה (מציאת האיבר הראשון):** בדומה לסעיף ג', העלות נשלטת על ידי הסריקה הראשונית של כל $n$ האיברים ברמה הנמוכה ביותר, ולכן היא $O(n)$. - **עלות עדכון (מציאת איבר נוסף):** הוצאת איבר דורשת עדכון בנתיב שעולה מהרמה התחתונה עד לרמה העליונה. ישנן $k$ רמות של קבוצות, ובכל רמה נדרש למצוא מינימום בקבוצה בגודל $b=n^{1/(k+1)}$. העלות הכוללת לעדכון היא $k \cdot O(n^{1/(k+1)})$. - **סיבוכיות כוללת:** $O(n) + n \cdot (k \cdot O(n^{1/(k+1)})) = O(k \cdot n^{1 + 1/(k+1)})$. ה. **ערך $k$ המקסימלי:** נתון כי גודל כל קבוצה בחלוקה חייב להיות לפחות 2. גודל הקבוצות הוא $b=n^{1/(k+1)}$. לכן, $n^{1/(k+1)} \ge 2$. ניקח $\log_2$ של שני האגפים: $\frac{1}{k+1} \log_2(n) \ge \log_2(2) = 1$ $\log_2(n) \ge k+1$ $k \le \log_2(n) - 1$ הערך השלם הגדול ביותר האפשרי עבור $k$ הוא $\lfloor \log_2(n) - 1 \rfloor$. **שיטת המיון המתקבלת:** עבור $k$ מקסימלי זה, גודל כל תת-קבוצה $b$ הוא 2. המבנה ההיררכי שנוצר הוא למעשה **עץ טורניר** (Tournament Tree), שהוא מבנה הדומה מאוד ל**ערימה בינארית**. בכל שלב, אנו משווים זוגות של איברים, ואז משווים את המנצחים ביניהם, וכן הלאה, עד לקבלת המינימום הכולל בפסגה (שורש העץ). גובה העץ הוא $O(\log n)$. הוצאת המינימום ועדכון המבנה (מציאת המינימום הבא) דורשת עדכון נתיב מהעלה לשורש, שעלותו $O(\log n)$. הסיבוכיות הכוללת למיון $n$ איברים היא $O(n \log n)$. זוהי סיבוכיות הזמן של **מיון ערימה (Heap Sort)**. $\blacksquare$