ניתוח משוערך (אמורטיזציה) - למה 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
שאלות נפוצות
מה זה ניתוח משוערך (אמורטיזציה)?
זו שיטה לחשב את העלות הממוצעת של פעולה על פני סדרה ארוכה של פעולות, במקום להסתכל על המקרה הגרוע הבודד. היא מתאימה כשפעולה יקרה מתרחשת לעיתים רחוקות ומאפשרת אחריה פעולות זולות רבות — ולכן המקרה הגרוע הבודד מציג תמונה מטעה לגבי העלות האמיתית.
למה הוספה למערך דינמי היא O(1) משוערך?
רוב ההוספות רק כותבות לתא פנוי — O(1). כשהמערך מתמלא, הוא מוכפל בגודלו וכל האיברים מועתקים — O(n). אבל הכפלה מבטיחה שהעתקה כזו מתרחשת רק אחרי n הוספות זולות, וסכום כל עלויות ההעתקה על פני n הוספות הוא לכל היותר 2n. מכאן שהעלות הממוצעת לפעולה קבועה.
מה ההבדל בין ניתוח משוערך לניתוח מקרה ממוצע?
ניתוח מקרה ממוצע מניח התפלגות הסתברותית על הקלטים ומחשב תוחלת, ולכן התוצאה היא הסתברותית. ניתוח משוערך אינו מניח דבר על הקלט — הוא נותן חסם דטרמיניסטי על סך העלות של כל סדרת פעולות אפשרית, מחולק במספרן. זו ערובה חזקה יותר.