קצב גדילה ו־O גדולה.

שלב 1 מתוך 6

להכפיל את הרשימה

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

שלב 2 מתוך 6

להכפיל עם מיון מיזוג

מיון בועות משווה זוגות, ומספר הזוגות גדל מהר. מיון מיזוג עובד אחרת: $\log_2 n$⁠ רמות, ובכל רמה עבודה פרופורציונית ל־$n$⁠. ביחד בערך $n \log_2 n$⁠.

שלב 3 מתוך 6

לוח הגדילה

הצגת קצב הגדילה על גדילה: מעל המדף עולה לוח זכוכית ועליו מספר ההשוואות מול גודל הרשימה. הסרט הכתום הוא $\dfrac{n(n-1)}{2}$⁠, כל הזוגות; הסרט הכחול הוא $n \log_2 n$⁠; הקו הלבן הוא האלגוריתם שבחרתם, בממוצע על כמה שורות התחלה; והנקודה היא המיון שרץ עכשיו.

שלב 4 מתוך 6

O גדולה

כדי לדבר על קצב גדילה בלי מספרים מדויקים, כותבים O גדולה: משאירים רק את האיבר שגדל הכי מהר, ומשמיטים מקדמים. חיפוש סדרתי הוא $O(n)$⁠, חיפוש בינארי $O(\log n)$⁠, ומיון מיזוג $O(n \log n)$⁠.

שנו את אלגוריתם ואת סדר התחלתי והשוו את הקו הלבן לשני הסרטים.

שלב 5 מתוך 6

למצוא את הגודל

כשהנוסחה ידועה, אפשר גם ללכת אחורה: מכמות העבודה לגודל הרשימה.

שלב 6 מתוך 6

אלגוריתם טוב יותר

ההבדל בין $n^2$⁠ ל־$n \log n$⁠ נראה קטן בשישים וארבעה בלוקים. במיליון הוא עצום: $\dfrac{n^2}{2}$⁠ הם כ־$5 \times 10^{11}$⁠, ו־$n \log_2 n$⁠ הם כ־$2 \times 10^7$⁠.