מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג/תרגילים/Combine Sort/תשובה

ראשית נראה שזמן הריצה במקרה הגרוע על קלט בגודל $\displaystyle i$,‏ $\displaystyle T(i)$, מקיים:

משפט: $\displaystyle T(i)=2\cdot T(i/2)+\Theta (i)$, אם $\displaystyle i>{\sqrt {n}}$. $\displaystyle T(i)=\Theta (n)$, אחרת.

הוכחה: אם $\displaystyle i>{\sqrt {n}}$ אז התנאי 1 לא מתקיים, ו4-7 מתבצעות. Combine-Sort, לכן, הופכת למעשה למיון מיזוג, שהיא בעלת נוסחת הנסיגה בנקודה הראשונה. מצד שני, אם התנאי ב1 אינו מתקיים, אז מופעל מיון הכנסה,על מערך שגודלו $\displaystyle {\sqrt {n}}$. במקרה הגרוע פועל מיון זה בזמן ריבועי בגודל הכניסה, ולכן כאן יעבוד בזמן $\displaystyle \Theta (({\sqrt {n}})^{2})=\Theta (n)$.

עלינו, על כן, לנתח נוסחה זו. נצייר את עץ הנסיגה:

עץ הפרישה לסוג זה של מיון.

בתרשים זה, נניח ש$\displaystyle h$ מציין את מספר הרמות עד שמגיעים לעלה (כלומר לארגומנט בגודל $\displaystyle {\sqrt {n}}$ בבעיה זו). מהו גובה העץ $\displaystyle h$? באופן דומה לגובה עץ פרישה בנוסחאות נסיגה,קל למדי להוכיח את הנקודות הבאות:

1. $\displaystyle h=1/2\cdot \log(n)\pm O(1)$.
2. כל רמה בעץ (למעט אולי האחרונה) תורמת $\displaystyle \Theta (n)$
3. מספר העלים הוא $\displaystyle 2^{1/2\cdot \log(n)\pm O(1)}=\Theta ({\sqrt {n}})$

משלוש נקודות אלו נוכל להסיק שתרומת הרמות הפנימיות היא $\displaystyle \Theta (n\cdot \log(n))$,‏ ותרומת העלים היא $\displaystyle \Theta ({\sqrt {n}}\cdot n)$. בסיכום נקבל‏ $\displaystyle \Theta ({\sqrt {n}}\cdot n)$.‏