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

דני שינה את תנאי העצירה של מיון מהיר ובמקום לכתוב $\text{if } p < r$ בשורה הראשונה הוא כתב $\text{if } p < r - k$ (שגרת מיון מהיר נמצאת בעמ' 122). בהנחה ש-$k$ הוא פרמטר לשגרה, מה יהיה זמן הריצה של מיון מהיר של דני במקרה הטוב ובמקרה הגרוע כפונקציה של $n$ ו-$k$?

רמז: הרקורסיה נעצרת כשגודל תת-המערך הוא $k$. במקרה הטוב החלוקה מאוזנת ועומק הרקורסיה הוא $\log(n/k)$. במקרה הגרוע החלוקה הכי גרועה.

פתרון: **מקרה טוב (חלוקה מאוזנת):** הרקורסיה נעצרת כאשר גודל תת-המערך $\leq k$. במקרה הטוב, הציר תמיד מחלק לשני חלקים שווים. נוסחת הנסיגה: $$T(n) = 2T(n/2) + O(n), \quad T(k) = O(1)$$ עומק הרקורסיה: $\log_2(n/k)$. בכל רמה עבודה $O(n)$. $$T(n) = O\left(n \log \frac{n}{k}\right)$$ **מקרה גרוע (חלוקה מקסימלית לא מאוזנת):** הציר תמיד הקטן/הגדול ביותר, ותת-מערך אחד בגודל 1 והשני $n-1$. נוסחת הנסיגה: $$T(n) = T(n-1) + O(n), \quad T(k) = O(1)$$ $$T(n) = \sum_{i=k+1}^{n} O(i) = O\left(\frac{n^2 - k^2}{2}\right) = O(n^2 - k^2)$$ עבור $k$ קבוע (או $k \ll n$): $$T(n) = O(n^2)$$ לסיכום: - **מקרה טוב:** $O(n \log(n/k))$ - **מקרה גרוע:** $O(n^2 - k^2)$, או בקירוב $O(n^2)$ כש-$k \ll n$.