ניתוח לשיעורין

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

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

היסטוריה

שיטת הניתוח לשיעורין פותחה על בסיס שיטת הצבירה אשר עכשיו היא חלק מניתוח לשיעורין. עם זאת, הטכניקה הוצגה רשמית לראשונה על ידי רוברט טרג'אן במאמרו "Amortized Computational Complexity" (סיבוכיות חישובית לשיעורין) אשר התייחס לצורך במציאת שיטה מועילה יותר לניתוח אלגוריתמים מאשר השיטות ההסתברותיות הנפוצות שהיו בשימוש. בתחילה, השיטה הייתה בשימוש עבור סוגים מאוד מסוימים של אלגוריתמים, במיוחד כאלה הכוללים שימוש בעצים בינאריים ופעולות איחוד. לעומת זאת, היום השיטה נפוצה מאוד ונמצאת בשימוש גם בניתוח סוגי אלגוריתמים רבים אחרים.

שיטה

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

1. שיטת הצבירה - מחשבים את החסם העליון $T(n)$ לעלות הכוללת של סדרה של $n$ פעולות ואז מגדירים את העלות לשיעורין כ-${\frac {T(n)}{n}}$.
2. שיטת החיובים - מחשבים את העלות של כל פעולה נפרדת ומשלבים את העלות המיידית של זמן הריצה שלה עם ההשפעה שלה על זמן הריצה של פעולות עתידיות. לרוב, פעולות רבות הרצות בזמן קצר צוברות "חוב" בתוספות קטנות בעוד שפעולות נדירות הרצות זמן רב מורידות אותו משמעותית.
3. שיטת הפוטנציאל - שיטה זו דומה לשיטת החיובים אך "מחייבת" פעולות בשלב מוקדם במחיר גדול מעלותן כדי לפצות על "חיובים" בשלב מאוחר יותר שיהיו נמוכים יותר מהעלות של הפעולות.

שלוש השיטות מספקות תוצאות זהות וההבדל בשימוש בהן הוא לרוב נסיבתי או תלוי-העדפה אישית.

שימוש נפוץ

• בשימוש השכיח, "אלגוריתם לשיעורין" הוא אלגוריתם שניתוח לשיעורין הראה שביצועיו טובים.
• בניתוח אלגוריתמים מקוונים נעשה שימוש רב בניתוח לשיעורין.

לקריאה נוספת

• גלעד אשרוב, ניתוח לשיעורין (עמ' 9), סיכום תרגול מספר 11 בקורס מבני נתונים באוניברסיטת בר-אילן, ‏2 ביוני 2013