ניתוח משוערך (אמורטיזציה) - למה ArrayList.add זה O(1)?
הסבר על ניתוח ממוצע על פני סדרת פעולות - קונספט שחיוני להבין מערכים דינמיים.
ניתוח Amortized (משוערך) בודק את העלות הממוצעת של פעולה כשמסתכלים על רצף ארוך של פעולות, ולא על מקרה גרוע בודד. זה מסביר למה פעולות שלכאורה יקרות נחשבות זולות ב'ממוצע'.
הדוגמה הקלאסית - מערך דינמי
ArrayList ב-Java או list בפייתון מתחילים בקיבולת קטנה. כשהם מתמלאים, מוקצה מערך חדש בגודל כפול ומעתיקים אליו את כל האלמנטים - פעולה ב-O(n).
אז למה אומרים ש-add היא O(1)? כי אחרי הכפלה, יש לנו n מקומות פנויים - n פעולות הבאות יהיו O(1). העלות של ההעתקה 'מתחלקת' על n פעולות, ולכן הממוצע הוא O(1).
חישוב מדויק
אחרי n הוספות, סך פעולות ההעתקה הוא 1 + 2 + 4 + 8 + ... + n/2 + n < 2n. סך כל הפעולות (כולל ההוספות עצמן) קטן מ-3n, ולכן ממוצע O(1) לפעולה.
המקרה הגרוע של add בודדת הוא עדיין O(n), אבל הממוצע על פני n פעולות הוא O(1). זה ההבדל בין worst case ל-amortized.
שיטות ניתוח
- Aggregate - מסכמים סך עלות ומחלקים במספר פעולות
- Accounting - מטעינים פעולות זולות ב'מטבעות' שמשלמים לפעולות יקרות
- Potential - מגדירים פונקציית פוטנציאל שמודדת מצב המבנה
דוגמאות נוספות
- Hash Table עם rehashing - insert ב-O(1) amortized
- Splay Tree - operations ב-O(log n) amortized
- Union-Find עם path compression - כמעט O(1) amortized