מבני נתונים תשס"ט/הרצאות/הרצאה 3

מתוך Coursebooks
קפיצה אל: ניווט, חיפוש

Quick Sort - מיון מהיר[עריכה]

נתחיל בגרסה בה נבחר pivot שרירותי (את האיבר הכי ימני למשל).

מיון מיזוג - עץ רקורסיה


(נניח לשם פשטות שכל הערכים במערך שונים).


פסאודו קוד[עריכה]

QuickSort(A, left, right)
1.   if left < right {
2.      m = partition(A, left, right);
3.      QuickSort(A, left, m-1);
4.      QuickSOrt(A, m+1, right);
5.   }

Partition(A, left, right)
1.   L = left;
2.   R = right;
3.   pivot = A[right];
4.   for j = left to right {
5.      if A[j] < pivot
6.         B[L] = A[j];
7.         L++;
8.      }
9.      if A[j] > pivot
10.        B[R] = A[j];
11.        R--;
12.     }
13.  }
14.  B[L] = pivot;
15.  A = B;
16.  return L;


inplace partition[עריכה]

נוכל לבצע את partition בצורה יעילה יותר (בעיקר מבחינת מקום).

נשמור 2 מצביעים: left ו- right.

א. נתחיל משמאל עד שנמצא איבר שגדול מה- pivot ונעצור.

ב. נמשיך מימין עד שנמצא איבר שקטן מה- pivot ונעצור.

ג. נחליף ביניהם.

ד. נמשיך שוב כל עוד left < right.

Partition(A, left, right)
1.   pivot = A[right];
2.   scan from left to right to find A[j] > pivot
3.   scan from right to left to find A[j] < pivot
4.   swap
5.   repeat until cross & insert pivot

משוואת הרקורסיה[עריכה]

נכתוב את משוואת הרקורסיה של QuickSort שהרגע ראינו:


\displaystyle T(n) = T(m-1) + T(n-m) + \Theta(n).


מקרים מיוחדים[עריכה]

נבחן 2 מקרים שונים בהם האלגוריתם מתנהג בצורות שונות זו מזו:


מקרה א[עריכה]

המקרה שבו החלוקה היא תמיד לחצי (כלומר \displaystyle m = \frac{n}{2}): \displaystyle T(n) = 2T(\frac{n}{2}) + \Theta(n)


נשים לב שמשוואה זו זהה למשוואת מיון המיזוג ולכן \displaystyle T(n)= \Theta(nlogn)

מקרה ב[עריכה]

המקרה שבו החלוקה היא תמיד ל- (1, n-2): \displaystyle T(n) = T(n-2) + \Theta(n) = \Theta(n^2)


סיבוכיות במקרה הגרוע ביותר (worst case)[עריכה]

ממוצע זמן הריצה עבור קלט שנבחר באקראי[עריכה]

קיימים n! קלטים אפשריים.

עבור פרמוטציה \displaystyle \sigma נקבל:

(*) \displaystyle <T(n)>   =   \frac{1}{n!}\sum_{\sigma}^{}T(n_\sigma).


מה קורה עבור רוב הקלטים? ניתן להוכיח (לא נוכיח) ש- \displaystyle <T(n)>   =   \Theta(nlogn).

בנוסף, ניתן להוכיח שאם נבחר קלט באקראי בהסתברות טובה הוא יהיה קלט "טוב" עם זמן ריצה \displaystyle \Theta(nlogn).


בהרבה מקרים המסקנה הזו לא טובה לנו. מדוע?

כי עדיין קיימים קלטים "גרועים" (או, "לא טובים").

כמו כן, הנחנו שהקלט נבחר באקראי אבל בהרבה מקרים הקלט לא יהיה כלל אקראי (למשל - מערך חצי ממויין) ולכן כן נרצה דרך טובה לבחון האם האלגוריתם הוא יעיל או לא.


מה נוכל לעשות? נכניס הסתברות לחישוב הסיבוכיות של האלגוריתם...


איך נכניס הסתברות לאלגוריתם? ב- QuickSort למשל נבחר את ה- pivot בצורה אקראית. ככה נקבל בעצם שאף קלט הוא לא ממש גרוע.


נדגיש שוב שיש הבדל רב מאוד בין זמן הריצה הממוצע על קלט אקראי לבין זמן ריצה ממוצע ע"ס הגרלות באלגוריתם, עבור כל קלט.


הסתברות[עריכה]

סיבות להבנת הסתברות[עריכה]

הסתברות וסטטיסטיקה על רגל אחת[עריכה]

מרחב מדגם[עריכה]

אוסף האפשרויות השונות לתוצאה של ניסוי.

לדוגמא:

בהטלת קוביה, מרחב המדגם הוא: {1,2,3,4,5,6}, מידת ההסתברות: \displaystyle \frac{1}{6}. בהטלת מטבע, מרחב המדגם הוא: {H, T}, מידת ההסתברות: \displaystyle \frac{1}{2}.


מאורע[עריכה]

קבוצה של מאורעות אלמנטריים.

ניתן לדבר על איחוד, חיתוך ומשלים של מאורעות.

לדוגמא: יצא מס' זוגי בהטלת קוביה.


תוחלת משתנה מקרי[עריכה]

\displaystyle E(X) = \sum_{j}jPr(X=j).

תוחלת היא לינארית, כלומר:

\displaystyle E(X+Y) = E(X) + E(Y)

\displaystyle E(aX+b) = aE(X)+b.

Randomized Quick Sort[עריכה]

נשתמש באלגוריתם זהה לזה שראינו בתחילת השיעור בו נשנה את דרך בחירת ה- pivot - הפעם נבחר pivot באקראי.


משוואת הרקורסיה[עריכה]

משוואת הרקורסיה עבור תוחלת זמן הריצה שלו היא:

(**) \displaystyle E[T(n)] = \frac{1}{n}\sum_{m=1}^{n}[E(T(m-1)) + E(T(n-m))] + \Theta(n).

ההבדל המהותי הוא שהאלגוריתם הראשון (*) מחושב על כל הקלטים האפשריים בעוד שבשני (**) הקלט קבוע.

איך מחשבים משהו כזה?

סיבוכיות זמן ריצה[עריכה]

\displaystyle E[T(n)] = \frac{1}{n}\sum_{m=1}^{n}[E(T(m-1)) + E(T(n-m))] + \Theta(n) = \frac{2}{n}\sum_{m=0}^{n-1}E[T(m)) + \Theta(n).


נכפול ב- n ונקבל:

\displaystyle nE[T(n)] = 2\sum_{m=0}^{n-1}[E(T(m))] + dn^2.


נציב n+1 ונקבל:

\displaystyle (n+1)E[T(n+1)] = 2\sum_{m=0}^{n}[E(T(m))] + d(n+1)^2.


נחסר את שתי המשוואות ונקבל:

\displaystyle (n+1)E[T(n+1)] - nE[T(n)] = 2E[T(n)] + d(n+1)^2 - dn^2.


ובסה"כ:

\displaystyle E[T(n+1)] = \frac{n+2}{n+1}E[T(n)] + \frac{d(n+1)^2 - dn^2}{n+1}.



הרצאה 3: QuickSort, חישוב המקרה הגרוע/ הממוצע, הסתברות
קורס מבני נתונים
המרצה פרופ' דורית אהרונוב
תאריך 22.3.2009
אורך שעה וחצי
חוג מדעי המחשב שנה א'
ההרצאה הקודמת הרצאה 2: עוד על אנליזה אסימפטוטית, אלגוריתמים רקורסיבים ושיטות חישוב
ההרצאה הבאה הרצאה 4: עוד על Randomized Quick Sort, מודל ההשוואות
תרגול רלוונטי תרגול 3: מבוא קצר לתורת ההסתברות
מבני נתונים - DAST
ספרות רשימת הספרים מופיעה באתר הקורס.
סיכומים באינטרנט אתר האגודה, האתר של דינה.
ערכים בוויקיפדיה העברית
ערכים בוויקיפדיה האנגלית