למה יש מיון מהיר יותר ממיון מהיר אבל בעצם אין

עד כה כל אלגוריתמי המיון שראינו פעלו בזמן של \( \Omega\left(n\log n\right) \), כלומר דרשו לפחות זמן ריצה אסימפטוטי של לפחות \( n\log n \) (כאשר \( n \) הוא גודל רשימת האיברים שאותה ממיינים). השאלה הראשונה שמתעוררת היא - האם אפשר טוב יותר מזה, או שכל אלגוריתם מיון ידרוש זמן ריצה של לפחות \( n\log n \) צעדים?

התשובה, כמו כל תשובה מעניינת במתמטיקה, היא “כן ולא”.

נתחיל מה”לא” - קיים אלגוריתם מיון פשוט ביותר שאציג עוד מעט שזמן הריצה שלו הוא \( \Theta\left(n\right) \). רק מה, האלגוריתם הזה הוא לא כללי; הוא חייב להניח הנחות מסויימות על אופי הקלט שלו. בפרט, הוא מניח שהוא ממיין רשימה של מספרים טבעיים. כמו כן, לומר שזמן הריצה שלו הוא \( \Theta\left(n\right) \) זו קצת רמאות כי יש עוד פרמטר שצריך לקחת בחשבון. למרות ההסתייגויות הללו, האלגוריתם הזה עובד מצוין בפועל, וכדאי לעתים קרובות להשתמש בו יותר מאשר כדאי להשתמש במיון מיזוג, או מיון מהיר, או מיון ערימה.

נעבור אל ה”כן” - קיימת הוכחה מתמטית לא מסובכת יותר מדי לפיה כל אלגוריתם מיון כללי ידרוש לפחות \( \Omega\left(n\log n\right) \) צעדי ריצה. מה זה אומר, “אלגוריתם כללי”? הכוונה כאן לאלגוריתם שהמידע היחיד שהוא יכול להפיק על אברי הרשימה שלו הוא מתוך השוואות של זוגות איברים. זה אומר שהאלגוריתם לא יכול להתבסס על ידע כלשהו לגבי ההתפלגויות האפשריות של האיברים ברשימה; ושהוא לא יכול לדעת שהם מספרים טבעיים או שלמים או כל דבר דומה. זו סיטואציה שאכן מתרחשת במקרים רבים בפועל, כך שהחסם התחתון הזה הוא ממשי מאוד.

נתחיל מהמיון, שנקרא “מיון ספירה” (Counting Sort). הרעיון הוא אידיוטי לגמרי: יש לכם רשימה של מספרים טבעיים ואתם רוצים למיין אותה? תעברו עליה איבר-איבר ותספרו כמה פעמים 0 מופיע, כמה פעמים 1 מופיע, וכן הלאה. אחרי שסיימתם, תבדקו כמה פעמים 0 הופיע ותכתבו כמספר הזה פעמים 0 לפלט; אחר כך תבדקו כמה פעמים 1 הופיע ותכתבו כמספר הזה פעמים 1 לפלט, וכן הלאה. הנה כל העסק בקוד:

def counting_sort(list)
  max = list.max
  values = [0] * (max + 1)
  for a in list
    values[a] += 1
  end
  pos = 0
  for i in 0...values.length
    for j in 0...values[i]
      list[pos] = i
      pos = pos + 1
    end
  end
  return list
end

מה זמן הריצה שלנו? הלולאה הראשונית, זו שבה סופרים כמה פעמים מופיע כל מספר ברשימה, דורשת \( O\left(n\right) \) זמן (וכך גם מציאת המקסימום שאני מבצע בשורה הראשונה). הלולאה השניה מעניינת קצת יותר, כי היא תלויה בערך של האיבר המקסימלי ברשימה. בואו נסמן בתור \( m \) את הערך הזה, אז הלולאה השניה מתבצעת בזמן של \( O\left(m+n\right) \) (למי שלא רואה את זה, שימו לב לכך ש-\( i \) רץ מאפס עד \( m \) ואילו \( pos \) רץ מאפס עד \( n \)). לכן זמן הריצה הכולל של האלגוריתם הוא \( O\left(n+m\right) \).

זה דבר חדש: זמן ריצה של אלגוריתם שתלוי בשני פרמטרים ולא באחד. כמובן, ייתכן שהערך של \( m \) הוא קבוע בכל הריצות של האלגוריתם, בלי תלות בגודל הרשימה (למשל, אם הרשימה היא תמיד של מספרי זהות); במקרים כאלו נכון לומר שזמן הריצה של האלגוריתם הוא פשוט \( O\left(n\right) \) ו”לשכוח” מהפרמטר \( m \) (למרות שהוא יבוא לידי ביטוי בקבוע גדול בפונקציה שמתארת את זמן הריצה בפועל).

שימו לב לכך שהאלגוריתם לא מבצע מיון במקום אלא דורש הקצאת זכרון נוסף - רשימה מאורך \( m \). זה לא חסרון מהותי עבור ערכים קטנים של \( m \), אבל אם הערכים האפשריים של \( m \) הם גדולים מדי זה הופך את האלגוריתם לבלתי ישים לחלוטין. למשל, עבור \( m=10^{12} \) האלגוריתם הוא כבר מאוד, מאוד בעייתי. לכן המיון הזה מבהיר יותר מכל מיון אחר עד כמה אין “מיון אחד נכון” שאפשר להשתמש בו להכל, ושהסיטואציה שבה אנחנו נמצאים חשובה. ארחיב על כך יותר בפוסט הבא בעניין.

נעבור לעניין השני שלנו - החסם התחתון של \( \Omega\left(n\log n\right) \) על מיון כללי. איך מוכיחים כזה דבר? באופן כללי, הוכחת חסמים תחתונים במדעי המחשב היא עניין קשה בהרבה מהוכחת חסמים עליונים. כדי להוכיח חסם עליון על זמן הריצה הנדרש לפתרון בעיה, כל מה שיש להציג הוא אלגוריתם אחד שפותר את הבעיה בזמן הריצה הזה; לעומת זאת, כדי להראות חסם תחתון על זמן הריצה יש להראות כי כל אלגוריתם שינסה לפתור את הבעיה יעשה זאת בזמן ריצה שהוא לפחות \( n\log n \). ההבדל הזה, של “קיים” אל מול “כל”, חוזר שוב ושוב במתמטיקה (ובחיים באופן כללי).

הדרך להתמודד עם הקושי הזה כאן היא למעט ככל הניתן בכניסה לפרטים הטכניים של “מה האלגוריתם בעצם עושה”, ולהתמקד בשאלה יותר פשוטה - כמה אינפורמציה האלגוריתם חייב להשיג על מנת להחזיר את הפלט הנכון ללא טעות? כדי להבין את הטענה הזו, בואו נעבור רגע לבעיה אחרת, פשוטה יותר - הבעיה של מציאת מקסימום ברשימה. אנחנו יודעים שאפשר למצוא מקסימום על ידי קריאת כל תא ברשימה בדיוק פעם אחת; האם אפשר פחות מזה?

התשובה האינטואיטיבית כאן היא “לא”. למה? כי נניח שקראנו את כל התאים ברשימה חוץ מאחד, ומבין כל התאים שקראנו, הערך המקסימלי שהיה בתוך תא הוא 13. אז מה? עדיין ייתכן שבתא היחיד שלא קראנו הערך יהיה 42, או 15, או כל דבר דומה שגדול מ-13, ולכן כל עוד לא קראנו את התא הזה פשוט אין לנו מספיק אינפורמציה כדי להחזיר את התשובה הנכונה.

קצת יותר פורמלית, אם יש לנו אלגוריתם שמחזיר את המקסימום מבלי לקרוא את כל התאים, אז אפשר לבנות קלט שיטעה את האלגוריתם. הטיעון הולך כך: נניח שיש לנו אלגוריתם למציאת מקסימום ברשימה כך שקיימת רשימה \( A \) שהאלגוריתם מחזיר עליה את התשובה הנכונה מבלי שיקרא את כל התאים. יהא \( k \) מספרו של תא שאותו האלגוריתם לא קורא, ויהא \( m \) הפלט של האלגוריתם על \( A \). נגדיר כעת רשימה חדשה \( B \) באופן הבא:

\( B\left[i\right]=\begin{cases}A\left[i\right] & i\ne k\\m+1 & i=k\end{cases} \)

כעת, על הקלט \( B \) האלגוריתם יחזיר בודאות את הפלט \( m \), שכן ההבדל היחיד בין \( A \) ובין \( B \) הוא בתוכן התא \( k \) שאותו האלגוריתם לא קורא. לכן האלגוריתם יתנהג על \( B \) בדיוק כפי שהיה מתנהג על \( A \) ויחזיר את הפלט \( m \) וזו כמובן טעות כי הערך המקסימלי ב-\( B \) הוא \( m+1 \).

בואו נעבור לטפל במיון באמצעות אותו רעיון, ולצורך כך נכניס לתמונה מושג מתמטי חדש: עץ החלטה. עץ החלטה (Decision Tree) הוא בעצם מודל מאוד פשטני של חישוב (כשהחישוב הוא על קלט כלשהו מאורך \( n \) - האורך של הקלט הוא חלק מהגדרת עץ ההחלטה הספציפי). זהו עץ בינארי שבו לכל צומת שאינו עלה יש שני בנים (הזכרתי עצים בינאריים בפוסט שדיבר על מיון ערימה). כל צומת פנימי מסומן על ידי פריט אחד של מידע מתוך הקלט שיכול להיות “כן” או “לא” (למשל, \( A\left[i\right]<A\left[j\right] \) עבור \( i,j \) מסוימים), ואילו העלים מסומנים על ידי פלטים אפשריים כלשהם. “חישוב” בעץ החלטה על קלט מסויים פועל כך: הוא מתחיל מהשורש, בודק את פריט המידע שמסומן בשורש, אם התשובה היא “כן” הוא הולך אל הבן הימני, ואם התשובה היא “לא” הוא הולך אל הבן השמאלי. כעת, אם הבן הוא עלה האלגוריתם פולט את הערך שכתוב בו; אחרת, האלגוריתם מבצע עוד בדיקה על בסיס הערך שכתוב בתוך הבן, ובוחר בן על פי התוצאה, וכן הלאה עד אשר מגיעים לעלים. כפי שאתם רואים, הרעיון פשוט עד אימה (או לחילופין, סתם מטיל אימה). הנקודה היא שכל אלגוריתם מיון כללי אכן ניתן לתאר באמצעות עץ החלטה שכזה, שבו פריטי המידע שבצמתים הם בדיוק השוואות בין זוג איברים ברשימה (כלומר, כל צומת מתאים לשאלה האם \( A\left[i\right]<A\left[j\right] \) עבור \( i,j \) מסויימים).

עכשיו, זמן הריצה של האלגוריתם חסום מלמטה על ידי עומק עץ ההחלטה (כי עומק עץ ההחלטה הוא בעצם “מספר ההשוואות המקסימלי שהאלגוריתם יבצע על קלט כלשהו”). נשאלת השאלה, אם כן, מה העומק המינימלי שיכול להיות בכלל לעץ החלטה שמתאים למיון קלט מגודל \( n \)? כדי לענות על זה צריך להבין כמה פלטים אפשריים צריכים להיות לעץ. פלט של אלגוריתם מיון הוא בעצם פרמוטציה של הקלט; לכל אינדקס ברשימה המקורית מותאם האינדקס של המקום החדש שאליו האיבר מועבר ברשימה החדשה. אם הרשימה היא מגודל \( n \), יש \( n! \) פרמוטציות (\( n! \) הוא סימון מקוצר ל-\( 1\cdot2\cdot3\cdots n \); הסיבה שיש \( n! \) פרמוטציות מוסברת בפוסט שלי על קומבינטוריקה בסיסית).

לא קשה להוכיח שהעץ הבינארי בעל העומק הקטן ביותר יחסית למספר הצמתים הוא עץ בינארי מלא - עץ שבו לכל צומת יש שני בנים עד לשכבה כלשהי שבה נמצאים כל העלים. אם עומק העץ הזה הוא \( k \), אז יש לו (חשבו!) בדיוק \( 2^{k} \) עלים. מכיוון שבעץ ההחלטה עבור מיון צריכים להיות \( n! \) עלים לפחות, אז צריך להתקיים \( 2^{k}\ge n! \), כלומר \( k\ge\lg n! \). זה מסיים את זה, בתנאי שאתם מאמינים לי ש-\( \lg n!=\Omega\left(n\log n\right) \).

אם אתם לא מאמינים, בואו נראה את זה. כמו תמיד, זה הופך להיות תרגיל נחמד בסכומים, שהוא כבר מתמטי טהור ולא קשור למדעי המחשב. ראשית כל, ללוגריתם יש את התכונה הנפלאה שהוא הופך מכפלה לחיבור, כלומר \( \log\left(a\cdot b\right)=\log a+\log b \). זה היה הרעיון הבסיסי שמאחורי סרגלי החישוב - עזרי חישוב מכניים נפלאים ויפהפיים שהפכו למיותרים לחלוטין עם המצאת המחשב, אבל זה לא גורע ממגניבותם. אני מקווה לכתוב על כך פוסט ביום מן הימים.

חזרה לענייננו. אם נשתמש בתכונה שלעיל, נהפוך את המכפלה לסכום: \( \lg\left(n!\right)=\lg\left(\prod_{k=1}^{n}k\right)=\sum_{k=1}^{n}\lg k \) (הסימן \( \Pi \) פשוט בא לתאר מכפלה בצורה מקוצרת, כשם ש-\( \Sigma \) בא לתאר סכום מקוצר). עכשיו, מפתה לומר ש-\( \lg k<\lg n \) לכל \( 1\le k\le n \) ולכן \( \sum_{k=1}^{n}\lg k\le\sum_{k=1}^{n}\lg n=n\lg n \) ולכן סיימנו, אבל רגע! זה בכלל לא מה שאנחנו רוצים לעשות! אנחנו רוצים חסם תחתון על הסכום, לא חסם עליון! הבלבול הקטן והמטופש הזה נפוץ בצורה יוצאת מן הכלל (וגם אני לוקה בו לעתים קרובות). אם כן, צריך משהו מחוכם קצת יותר; מה הוא יהיה? תעלול די סטנדרטי: לחלק את הסכום לשני חלקים.

אם כן, \( \sum_{k=1}^{n}\lg k\ge\sum_{k=\left\lceil \frac{n}{2}\right\rceil }^{n}\lg k \) - כאן זרקתי את כל החצי הראשון של האיברים בסכום, כי הם לא גדולים במיוחד אז למי אכפת מהם. כעת אני יודע שהאיבר הקטן ביותר בסכום הוא \( \lg\left\lceil \frac{n}{2}\right\rceil \), ויש בסכום \( \left\lfloor \frac{n}{2}\right\rfloor \) איברים, ולכן \( \sum_{k=1}^{n}\lg k\ge\left\lfloor \frac{n}{2}\right\rfloor \lg\left\lceil \frac{n}{2}\right\rceil \ge\left\lfloor \frac{n}{2}\right\rfloor \lg n-2\left\lfloor \frac{n}{2}\right\rfloor =\Omega\left(n\log n\right) \). זה מסיים את העניין סופית.

אם לסכם, הטיעון הוא “אם לא ביצעת סדר גודל של \( n\log n \) השוואות, לא קיבלת מספיק אינפורמציה על הקלט כדי להיות מסוגל להכריע בודאות איך למיין אותו. שימו לב שאף פעם לא צריך את כל האינפורמציה, כלומר את כל \( {n \choose 2} \) ההשוואות של איברים, מה שהיה מסדר גודל של \( \Theta\left(n^{2}\right) \); הרי אפשר להסיק אינפורמציה נוספת מתוך מה שקראנו ישירות מהקלט. כך למשל אם גילינו ש-\( A\left[i\right]<A\left[j\right] \) ו-\( A\left[j\right]<A\left[k\right] \) אז אפשר להסיק ש-\( A\left[i\right]<A\left[k\right] \) (זוהי הטרנזיטיביות של יחס הסדר). מיון מהיר משתמש בתכונה הזו בצורה מאוד מפורשת - כל ההשוואות הן תמיד ל”איבר ציר” מתוך הנחה שאם יש לנו שני איברים כך שהראשון קטן מאיבר הציר והשני גדול ממנו, אז האיבר הראשון קטן מהשני. מיון מיזוג ומיון ערימה משתמשים בהנחה הזו באופן קצת יותר מעודכן, וזה תרגיל נחמד לבדוק איפה היא בדיוק צצה.