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

[2] יהיו $A, B$ אלגוריתמי מיון מבוססי השוואות. הוכיחו או הפריכו כל אחת מהטענות הבאות: א) (10 נקודות) יתכן שזמן הריצה של האלגוריתם A במקרה הגרוע הוא $n \cdot \log n \cdot \log(\log n)$. ב) (15 נקודות) במרבית המקרים (כלומר על יותר ממחצית הקלטים בגודל $n$) האלגוריתם B ירוץ בזמן לינארי.

רמז: מהו החסם התחתון התאורטי לסיבוכיות של מיון מבוסס השוואות במקרה הגרוע? האם הסיבוכיות הנתונה סותרת חסם זה?

פתרון: הטענה נכונה. **החסם התחתון** על זמן הריצה של אלגוריתם מיון מבוסס השוואות במקרה הגרוע הוא $\Omega(n \log n)$. חסם זה נובע ממודל **עץ ההחלטה**, שבו כל עלה מייצג תמורה אפשרית אחת של הקלט, ולכן חייבים להיות לפחות $n!$ עלים. גובה העץ, המייצג את מספר ההשוואות במקרה הגרוע, הוא לכן לפחות $\log_2(n!) = \Omega(n \log n)$. הסיבוכיות הנתונה היא $T(n) = n \cdot \log n \cdot \log(\log n)$. נבדוק האם סיבוכיות זו עומדת בחסם התחתון. כלומר, האם $n \cdot \log n \cdot \log(\log n) \in \Omega(n \log n)$? על פי הגדרת סימון $\Omega$, עלינו למצוא קבוע $c > 0$ ו-$n_0$ כך שלכל $n > n_0$ מתקיים: $n \cdot \log n \cdot \log(\log n) \ge c \cdot n \log n$ נחלק את שני האגפים ב-$n \log n$ (עבור $n>1$): $\log(\log n) \ge c$ מאחר שהפונקציה $\log(\log n)$ שואפת לאינסוף כאשר $n$ שואף לאינסוף, לכל קבוע $c$ שנבחר, קיים $n_0$ כך שהאי-שוויון מתקיים לכל $n > n_0$. לדוגמה, עבור $c=1$, האי-שוויון מתקיים כאשר $\log_2(\log_2 n) \ge 1$, כלומר $\log_2 n \ge 2$, כלומר $n \ge 4$. מכיוון שהסיבוכיות הנתונה אינה סותרת את החסם התחתון התאורטי, ייתכן אלגוריתם כזה. אלגוריתם כזה יהיה לא יעיל (יותר איטי מאלגוריתמים אופטימליים כמו מיון מיזוג), אך הוא אפשרי תאורטית. $\blacksquare$