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