הגדרה של עלות ממוצעת

[johnny d]

הגדרה של עלות ממוצעת

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

 

[אמיתי ר]

הוא צודק...

אבל רק בערך (לפי הבנתי). הקבלה מסוימת שאני יכול לחשוב עליה זה עלות לשיעורין זה ממוצע משוקלל, בעוד עלות ממוצעת זה "ממוצע" בלבד. והרי מה ההבדל? שאם יש לך 3 פעולות, אז ממוצע, זה פשוט ממוצע הזמן שלוקח לשלושתם לפעול בלי שום התחשבות נוספת (לא ממש שמיש במדמ"ח, עד כמה שידוע לי, ולכן המושג איננו נמצא ברוב הספרים/ המקורות) בעוד עלות לשיעוריון מתחשבת, כמו ממוצע משוקלל (או תוחלת נניח בהסתברות) בכמות ההופעות של פעולה אחת יחסית לשניה. (לדוגמה, 10 פעולות הוספה, 4 פעולות מחיקה, 6 פעולות מיון בלה בלה)

 

[johnny d]

זה ממש לא נכון

אתה מדבר על טכניקה לניתוח מערכות סגורות. ממוצע זה עלות של x פעולות לחלק למספר הפעולות, ולמעשה ההגדרה של עלות לשיעורין (לפי MIT) היא עלות ממוצעת של פעולה !!!

 

[vinney]

אולי יש מושג שנקרא עלות ממוצעת

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

 

[johnny d]

דיברתי איתו היום

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

 

[vinney]

זה משהו אחר ../images/Emo13.gif

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