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

מיון מהיר (quicksort או QS בקיצור) פועל ע"י (1) בחירת איבר חלוקה $K$ (שמטעמי עצלות נבחר לעיתים קרובות כ־$K = A[1]$), (2) חלוקת $n$ האיברים במערך $A$ ל־2 קבוצות $S_1$ ו־$S_2$ שמכילות, בהתאמה, את האיברים הקטנים מ־$K$ ואת האיברים הגדולים מ־$K$ וסידור המערך מחדש ל־$S_1, K, S_2$, ז"א $K$ במקומו המיועד, משמאלו איברי $S_1$ ומימינו איברי $S_2$, ו־(3) המשך רקורסיבי על $S_1$ ועל $S_2$. הוכח/י שמיון מהיר אופטימלי בממוצע, כאשר בכל השאלה הממוצע מתייחס לכך שהמיקום בסידור הממויין של איבר החלוקה יכול להיות בכל אחד מ־$n$ המקומות, בהסתברות שווה. הדרכה: נגדיר $T(n)$ - מספר השוואות ממוצע כדי למיין $n$ איברים ע"י QS. א) $T(n) = a(n) + b(n) \sum_{i=1}^n c(i)$ כאשר $a(n) = n+1$ הוא מספר ההשוואות לביצוע החלוקה, $b(n) = \frac{1}{n}$ היא ההסתברות שאיבר החלוקה יפול למקום ה־$i$, ו־$c(i)$ היא עלות ההמשך הרקורסיבי במקרה שאיבר החלוקה יפול למקום ה־$i$, ועליכם למצוא את $c(i)$ במונחים של $T$. רשמו את הנוסחה הרקורסיבית שמתקבלת עבור $T(n)$. ב) הכפל/י את 2 צידי המשוואה ב־$n$ כדי לטפל רק במספרים שלמים. ג) נסחו משוואה דומה אך שונה: עם פרמטר $n-1$ במקום $n$. ד) צרו משוואה חדשה ע"י חיסור אגף אגף של המשוואות הקודמות, וסידור מחדש. ה) חלקו את שני האגפים ב־$(n+1)n$. ו) הגדירו $H(n) = \frac{T(n)}{n+1}$, וקבלו נוסחה רקורסיבית עבור $H(n)$. ז) פתרו עבור $H(n)$ והסיקו ל־$T(n)$. מה המסקנה בענין האופטימליות של QS?

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

פתרון: נוכיח כי **מיון מהיר (Quicksort)** הוא אופטימלי בממוצע על ידי פיתוח ופתרון נוסחת נסיגה למספר ההשוואות הממוצע, $T(n)$. נעקוב אחר שלבי ההדרכה. **א) ניסוח נוסחת הנסיגה עבור $T(n)$** $T(n)$ הוא מספר ההשוואות הממוצע למיין $n$ איברים. על פי הנתון, שלב החלוקה דורש $a(n) = n-1$ השוואות (כל איבר מושווה לאיבר החלוקה). בנוסף, איבר החלוקה $K$ יכול ליפול לכל אחד מ-$n$ המקומות האפשריים בסידור הממוין, בהסתברות שווה של $b(n) = \frac{1}{n}$. אם איבר החלוקה נופל למקום ה-$i$ (כלומר, הוא האיבר ה-$i$ בגודלו), המערך מתחלק לשתי תת-בעיות: מיון תת-מערך בגודל $i-1$ (האיברים הקטנים מ-$K$) ומיון תת-מערך בגודל $n-i$ (האיברים הגדולים מ-$K$). העלות הממוצעת של ההמשך הרקורסיבי, $c(i)$, היא סכום העלויות של שתי תת-הבעיות: $c(i) = T(i-1) + T(n-i)$. לפיכך, נוסחת הנסיגה המלאה היא: $T(n) = (n-1) + \frac{1}{n} \sum_{i=1}^{n} (T(i-1) + T(n-i))$ נפשט את הסכום: $\sum_{i=1}^{n} (T(i-1) + T(n-i)) = (T(0)+T(n-1)) + (T(1)+T(n-2)) + ... + (T(n-1)+T(0)) = 2 \sum_{j=0}^{n-1} T(j)$ נציב חזרה ונקבל את הנוסחה הרקורסיבית עבור $T(n)$, כאשר תנאי הבסיס הם $T(0)=T(1)=0$: $T(n) = n-1 + \frac{2}{n} \sum_{j=0}^{n-1} T(j)$ **ב) הכפלה ב-$n$** כדי להיפטר מהשבר, נכפיל את שני אגפי המשוואה ב-$n$ (עבור $n \ge 2$): $n T(n) = n(n-1) + 2 \sum_{j=0}^{n-1} T(j)$ **ג) ניסוח משוואה עבור $n-1$** נרשום את המשוואה מסעיף ב' עבור $n-1$ (עבור $n-1 \ge 2$, כלומר $n \ge 3$): $(n-1) T(n-1) = (n-1)(n-2) + 2 \sum_{j=0}^{n-2} T(j)$ **ד) חיסור וסידור מחדש** נחסר את המשוואה מסעיף ג' מזו של סעיף ב': $n T(n) - (n-1) T(n-1) = [n(n-1) + 2 \sum_{j=0}^{n-1} T(j)] - [(n-1)(n-2) + 2 \sum_{j=0}^{n-2} T(j)]$ $n T(n) - (n-1) T(n-1) = n(n-1) - (n-1)(n-2) + 2 T(n-1)$ $n T(n) - (n-1) T(n-1) = (n-1)(n - (n-2)) + 2 T(n-1)$ $n T(n) - (n-1) T(n-1) = 2(n-1) + 2 T(n-1)$ נסדר מחדש את המשוואה: $n T(n) = (n-1)T(n-1) + 2T(n-1) + 2(n-1)$ $n T(n) = (n+1) T(n-1) + 2(n-1)$ **ה) חלוקה ב-$n(n+1)$** נחלק את שני אגפי המשוואה האחרונה בביטוי $n(n+1)$: $\frac{n T(n)}{n(n+1)} = \frac{(n+1) T(n-1)}{n(n+1)} + \frac{2(n-1)}{n(n+1)}$ $\frac{T(n)}{n+1} = \frac{T(n-1)}{n} + \frac{2(n-1)}{n(n+1)}$ **ו) הגדרת $H(n)$ וקבלת נוסחה עבורו** נגדיר משתנה עזר $H(n) = \frac{T(n)}{n+1}$. נשים לב ש-$H(n-1) = \frac{T(n-1)}{n}$. נשתמש בפירוק לשברים חלקיים עבור האיבר האחרון: $\frac{2(n-1)}{n(n+1)} = \frac{4}{n+1} - \frac{2}{n}$. נציב את $H(n)$ ואת הפירוק במשוואה מסעיף ה': $H(n) = H(n-1) + \frac{4}{n+1} - \frac{2}{n}$ **ז) פתרון עבור $H(n)$ ו-$T(n)$ והסקת מסקנות** קיבלנו נוסחת נסיגה פשוטה ל-$H(n)$. נפתור אותה באמצעות **סכום טלסקופי**: $H(n) = H(1) + \sum_{k=2}^{n} (\frac{4}{k+1} - \frac{2}{k})$ תנאי הבסיס הוא $T(1)=0$, ולכן $H(1) = \frac{T(1)}{1+1} = 0$. $H(n) = \sum_{k=2}^{n} (\frac{4}{k+1} - \frac{2}{k}) = 2 \sum_{k=2}^{n} (\frac{2}{k+1} - \frac{1}{k})$ זהו אינו סכום טלסקופי פשוט, אך ניתן לחשב אותו כ: $H(n) = 2 \sum_{k=2}^{n} \frac{1}{k+1} + 2 \sum_{k=2}^{n} (\frac{1}{k+1} - \frac{1}{k})$ $H(n) = 2 \sum_{j=3}^{n+1} \frac{1}{j} + 2 (\frac{1}{n+1} - \frac{1}{2}) = 2 (H_{n+1} - 1 - \frac{1}{2}) + 2 (\frac{1}{n+1} - \frac{1}{2}) = 2H_{n+1} - 3 + \frac{2}{n+1} - 1 = 2H_{n+1} - 4 + \frac{2}{n+1}$ כאשר $H_{m} = \sum_{i=1}^{m} \frac{1}{i}$ היא **הסדרה ההרמונית**, והיא מקיימת $H_m \approx \ln(m)$. לכן, $H(n) \approx 2\ln(n+1) - 4$. אסימפטוטית, $H(n) \in \Theta(\log n)$. כעת נמצא את $T(n)$: $T(n) = (n+1) H(n) \approx (n+1)(2\ln(n+1) - 4)$ מכאן, הסיבוכיות הממוצעת של מיון מהיר היא $T(n) \in \Theta(n \log n)$. **מסקנה לגבי אופטימליות:** כל **אלגוריתם מיון מבוסס השוואות** דורש לפחות $\Omega(n \log n)$ השוואות במקרה הממוצע. הוכחה זו מתבססת על ניתוח **עץ ההחלטה** של המיון. מכיוון שסיבוכיות הזמן הממוצעת של מיון מהיר היא $\Theta(n \log n)$, היא תואמת את החסם התחתון התיאורטי. לכן, **מיון מהיר הוא אסימפטוטית אופטימלי במקרה הממוצע**. $\blacksquare$