מבוא לתכנות ולמדעי המחשב בשפת C/רקורסיה (מיון מהיר): הבדלים בין גרסאות בדף

מ
imported>איתמר לנדסמן
בשיעור זה נלמד אלגוריתם יעיל בהרבה שנקרא מיון מהיר, או quicksort בלעז. בממוצע, הסיבוכיות של האלגוריתם הזה היא <m>O(n \cdot log (n))</m> אבל במקרה הכי גרוע (והנדיר) היא עדיין <m>O(n^2)</m>.
 
עד היום דיברנו על סיבוכיות התלויה רק בגודל הקלט. כאן, כשארכאשר תיארנו את הסיבוכיות של quicksort, דיברנו על סיבוכיות ממוצעת וסיבוכיות במקרה הגרוע. העניין הוא שיעילות האלגוריתם שנלמד עכשיו, תלויה מאוד בסדר הנתונים שהתקבלו בקלט. לדוגמה, דווקא אם הקלט יהיה ממויין מלכתחילה, האלגוריתם יעבוד קשה מאוד והיעילות שלו תהיה דומה לזו של המיון הנאיבי שלמדנו. במקרה היותר טיפוסי, של קלט מעורבל, האלגורתם יהיה יעיל בהרבה.
כאשר באים לבחור אלגוריתם, לרוב מתעניינים בעיקר ביעילות הממוצעת מכיוון שנתון זה מלמד כמה זמן תמשכנה הפעלות רבות של האלגוריתם. למרות זאת, לפעמים, יש מצבים שבהם אנחנו רוצים להיות בטוחים שהאלגוריתם מסיים תוך זמן ידוע, בגלל גורמים נוספים התלויים בו, ואז נתעניין דווקא בזמן הגרוע ביותר.