שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2020 - מיון

נשנה את שגרת החלוקה של מיון-מהיר באופן דומה, אך הפעם נבחר כאיבר ציר את **ערך המיקום** ה-$\lfloor n/8 \rfloor$ (כלומר האיבר הקטן ביותר בתת-המערך הנ"ל). מהו זמן הריצה של האלגוריתם מיון-מהיר במקרה זה? הוכיחו את טענתכם.

רמז: חשבו: אם תמיד בוחרים את האיבר ה-$\lfloor n/8 \rfloor$ בגודלו כציר, מה הפיצול?

פתרון: **ניתוח:** הפעם הציר הוא האיבר ה-$\lfloor n/8 \rfloor$ בגודלו מבין כל האיברים (מכיוון שזהו המינימום של תת-המערך $A[\lfloor n/8 \rfloor + 1..n-\lfloor n/8 \rfloor]$, שהוא האיבר ה-$\lfloor n/8 \rfloor + 1$ בגודלו, בקירוב ה-$n/8$). החלוקה תהיה: - צד אחד: $\lfloor n/8 \rfloor \approx n/8$ איברים - צד שני: $n - \lfloor n/8 \rfloor - 1 \approx 7n/8$ איברים נוסחת הנסיגה: $$T(n) = T(n/8) + T(7n/8) + \Theta(n)$$ זוהי בדיוק אותה נוסחה כמו בסעיף א'! (סדר החיבור לא משנה.) לכן, באותו אופן בדיוק, ניתן להראות: **התשובה: $T(n) = \Theta(n \log n)$.** ההוכחה זהה לסעיף הקודם – החלוקה היא באותו יחס $1/8$ מול $7/8$, ולכן עץ הרקורסיה מתנהג באותו אופן.