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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי



ראשית נראה שזמן הריצה במקרה הגרוע על קלט בגודל ,‏ , מקיים:



משפט:

  1. , אם .
  2. , אחרת.



הוכחה: אם אז התנאי 1 לא מתקיים, ו4-7 מתבצעות. Combine-Sort, לכן, הופכת למעשה למיון מיזוג, שהיא בעלת נוסחת הנסיגה בנקודה הראשונה. מצד שני, אם התנאי ב1 אינו מתקיים, אז מופעל מיון הכנסה,על מערך שגודלו . במקרה הגרוע פועל מיון זה בזמן ריבועי בגודל הכניסה, ולכן כאן יעבוד בזמן .

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

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

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

  1. .
  2. כל רמה בעץ (למעט אולי האחרונה) תורמת
  3. מספר העלים הוא

משלוש נקודות אלו נוכל להסיק שתרומת הרמות הפנימיות היא ,‏ ותרומת העלים היא . בסיכום נקבל‏ .‏