التحليل المطفأ يقيس متوسط التكلفة لكل عملية على سلسلة من العمليات، حتى عندما تكلف العمليات الفردية أحياناً أكثر بكثير. فهو يشرح لماذا تكون عملية append في المصفوفة الديناميكية "O(1) amortized" على الرغم من إعادة تحجيم O(n) العرضية.
عندما تمتلئ المصفوفة الديناميكية، تقوم بتخصيص مصفوفة جديدة (عادة ) وتنسخ جميع العناصر — وهي خطوة O(n). لكن لأن السعة تتضاعف، تصبح عمليات النسخ المكلفة نادرة جداً من الناحية الأسية.
Appending into a doubling array (cap shown):
ops: 1 2 3 4 5 6 7 8 9
cap: 1 2 4 4 8 8 8 8 16
copy: * * * * * <- copies at 1,2,4,8,16...
To insert n elements, total copy work =
1 + 2 + 4 + ... + n ≈ 2n (geometric series)
Total cost for n inserts = O(n)
Amortized cost per insert = O(n)/n = O(1)
arr = []
for i in range(1_000_000):
arr.append(i) # almost always O(1); rarely O(n) during a resize
| العملية | الأسوأ حالة واحدة | المطفأ |
|---|---|---|
| append (doubling) | O(n) | O(1) |
النمو بمقدار ثابت سيؤدي إلى تفعيل نسخة في كل إدراج، مما يعطي O(n) مطفأ. النمو المضروب هو ما يوزع التكلفة.
يعطي التحليل المطفأ صورة عادلة وواقعية للأداء — بدونه، ستخاف بشكل خاطئ من أن كل append أو إدراج في جدول hash هو O(n).
كما أنه يبرر قاعدة تصميم رئيسية: نمو السعة بشكل مضروب، وهو ما يكمن وراء المصفوفات الديناميكية وجداول hash ومُنشئي الأسلاك في كل مكان.
مكتبة من أسئلة مقابلات تقنية المعلومات مع إجابات مفصّلة — من المبتدئ إلى المتقدم.
تبرع