קצת מדמ"ח...

[Starving Marvin]

קצת מדמ"ח...

שאלה שמטרידה אותי, ברשותכם: כיצד מודדים סיבוכיות למקרה הממוצע, ולאילו מטרות יעשה הדבר?

 

[ה עוד אחד]

תראה...

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

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

 

[Starving Marvin]

מממ.

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

 

[mandymo]

בד"כ

במיון, בד"כ לא תקבל את הקלט ממויין (או ממויין הפוך) שזה המקרה הגרוע עבור QS. ולכן מתיחסים למקרה הממוצע. המיקרה הממוצע הוא הקשה ביותר לחישוב, כי באמת - מהו המקרה הממוצע - דבר שעוזר לחוסר הפופולריות שלו. בכללי, המקרה הממוצע מוגדר כתוחלת של הסיבוכיות (זוכר סטטיסטיקה???) במיקרה של QS, ניתן לראות שגם אם הקלט ממויין ביחס של 2:8, לדוגמה, הסיבוכיות שלו טובה, וזה מיקרה הרבה יותר "ממשי" מאשר קלט ממויין, ולכן הוא מחשב כמיון יעיל.