מציאת חסם תטא של מיון מהיר

[אלעד יחזקאל‎]

http://en.wikipedia.org/wiki/Quicksort

אחרי קריאה פה הם מחלקים לשני מצבי קיצון

1. הרשימה כבר ממוינת ואז

T(n)=T(n-1) + T(1) + n

ואז יש לנו סדרה חשבונית בלה בלה ואז O(n^2)

2. הפיווט שניקח תמיד יחלק את הרשימה לשתיים ואז

T(n)=2T(n/2) + n

ואז לפי תיאוריית האב O(nlogn)

איך אני משלב בין המצבי קיצון האלה כדי להשיג חסם תטא?

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

[Avichai Marmor]

שלום,

באלגוריתם שאתה מציג, חסם נקבע על פי worst case, ולכן זה Theta(n^2) . למרות זאת, במקרה הממוצע זה nlog n עם מקדם נמוך, ולכן באופן פרקטי זה שימושי.

האלגוריתם שראינו בהרצאה טיפה שונה: בכל שלב, מגרילים איבר מהמערך (ולא לוקחים דווקא את הראשון). כך, לכל מערך, נסיים ב n log n בהסתברות גבוהה, ולכן נקבל Theta(n*log n).

מקווה שעזרתי.

[אלעד יחזקאל‎]

לא חידשת כלום

מה התטא?

[Avichai Marmor]

באלגוריתם שאתה מדבר עליו - n^2.

באלגוריתם שראינו בהרצאה - n*log(n)