לבחור אום אחד באקראי ולנסות להתאים אותו לכל אחד מ-n הברגים. במקרה הגרוע נמצא התאמה רק בבורג באחרון.
לאחר מכן, לקחת אום שרירותי אחריו ולנסות להתאים אותו לכל אחד מ-n-1 הברגים הנותרים. שוב, במקרה הכי גרוע נמצא התאמה גם רק בבורג האחרון...
ככה עד אשר התאמנו את כולם
זמן הריצה:
c*(n+n-1+n-2+n-3+...+1)
O(n^2)
|
ע״י המידע הנוסף של הגדלים, ניתן להשתמש כאן בווריאציה של quicksort ע״מ להגיע לזמן ריצה ממוצע של O(n*log2n).
קח בחשבון שגם עבור quicksort, המקרה הגרוע ביותר עדיין מאלץ את האלגוריתם לעבוד ב-O(n^2) פעולות, אבל לרוב הוא יעבוד ב-O(n*log2n)
He who makes a beast out of himself,
gets rid of the pain of being a man.
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
