تحلیل مستهلک: روش تجمعی، روش حسابداری، و روش پتانسیل

چرا تحلیل مستهلک با تحلیل حالت‌میانگین متفاوت است

تحلیل حالت‌میانگین که پیش‌تر در این مجموعه، در زمینه تحلیل احتمالاتی، بحث شد، برخی توزیع احتمالی روی ورودی‌ها فرض می‌کند و درباره رفتار مورد انتظار استدلال می‌کند. Amortized Analysis (تحلیل مستهلک) کاملاً متفاوت است: هیچ فرض احتمالاتی‌ای نمی‌کند. در عوض، میانگین هزینه به‌ازای هر عملیات را در سراسر یک توالی بدترین‌حالت از عملیات‌ها تضمین می‌کند، و یک کران دقیق و قطعی به‌جای یک امید ریاضی احتمالاتی فراهم می‌کند.

مثال انگیزاننده: آرایه پویا

یک آرایه پویا (مانند آن‌هایی که زیربنای انواع لیست داخلی بسیاری زبان‌های برنامه‌نویسی هستند) را در نظر بگیرید که خالی شروع می‌شود و ظرفیتش را با دوبرابرکردن هروقت پر شود رشد می‌دهد. یک درج واحد که یک تغییر اندازه را فعال می‌کند نیازمند کپی‌کردن هر عنصر موجود در آرایه جدید و بزرگ‌تر است — یک عملیات O(n) گران. با این حال، از نظر شهودی، این تغییر اندازه گران به‌اندازه کافی به‌ندرت رخ می‌دهد که هزینه میانگین به‌ازای هر درج باید کوچک باشد. تحلیل مستهلک این شهود را از نظر ریاضی دقیق می‌کند.

روش تجمعی: هزینه کل تقسیم بر تعداد عملیات

Aggregate Method (روش تجمعی) هزینه کل بدترین‌حالت یک توالی از n عملیات را محاسبه می‌کند، سپس بر n تقسیم می‌کند تا هزینه مستهلک به‌ازای هر عملیات به دست آید.

برای آرایه پویا که از اندازه 1 دوبرابر می‌شود:
تغییر اندازه‌ها در درج‌های 1، 2، 4، 8، 16، ...، 2^k رخ می‌دهند

هزینه درج i (نادیده‌گرفتن خود درج O(1)):
0 اگر i توان 2 نباشد (تغییر اندازه‌ای نیاز نیست)
i اگر i توان 2 باشد (باید i عنصر را در طول تغییر اندازه کپی کند)

هزینه کل n درج:
n · O(1)  (برای n درج معمولی)
+ Σ (j=0 تا log n) 2^j   (برای کپی‌های تغییر اندازه)
= n + (2^(⌊log n⌋+1) - 1)
< n + 2n = 3n

هزینه مستهلک به‌ازای هر عملیات: 3n / n = O(1)

با وجود اینکه درج‌های منفرد گاهی Θ(n) هزینه دارند، هزینه مستهلک به‌ازای هر درج در سراسر هر توالی از n درج O(1) است — تضمینی که برای هر توالی ممکن برقرار است، نه صرفاً به‌طور میانگین در سراسر ورودی‌های تصادفی.

روش حسابداری: پیش‌پرداخت برای عملیات‌های گران آینده

Accounting Method (روش حسابداری) به هر عملیات یک Amortized Cost (هزینه مستهلک) اختصاص می‌دهد، که ممکن است با هزینه واقعی‌اش متفاوت باشد. عملیات‌های ارزان کمی بیشتر از هزینه واقعی‌شان شارژ می‌شوند، و یک موجودی "اعتبار" جمع می‌کنند، در حالی که عملیات‌های گران این اعتبار ذخیره‌شده را برای پوشش هزینه واقعی بالاتر خود برمی‌دارند. نیاز کلیدی این است که موجودی اعتبار کل هرگز در هیچ نقطه‌ای در توالی نباید منفی شود.

برای آرایه پویا، به هر درج یک
هزینه مستهلک 3 اختصاص بده (هرچند هزینه
واقعی معمولاً فقط 1 است):

1 واحد خود درج را می‌پردازد
2 واحد به‌عنوان اعتبار ذخیره می‌شود

وقتی یک تغییر اندازه در اندازه n رخ می‌دهد (دوبرابرشدن از n به 2n)،
تغییر اندازه باید n عنصر را کپی کند. اما دقیقاً n عنصر
از آخرین تغییر اندازه (وقتی آرایه از n/2 به n رشد کرد) درج شده‌اند،
هرکدام 2 اعتبار ذخیره کرده‌اند، که در مجموع 2n اعتبار فراهم می‌کند —
که به‌راحتی هزینه کپی n-عنصر را می‌پوشاند

از آنجا که هر عملیات یک هزینه مستهلک ثابت ۳ شارژ می‌شود، و اثبات شده اعتبار انباشته پیش از نیاز هرگز تمام نمی‌شود، این همان کران مستهلک O(1) پیداشده توسط روش تجمعی را تأیید می‌کند، اما از طریق یک استدلال متفاوت و اغلب شهودی‌تر.

روش پتانسیل: یک تشبیه انرژی فیزیکی

Potential Method (روش پتانسیل) یک Potential Function (تابع پتانسیل) Φ تعریف می‌کند که وضعیت فعلی ساختار داده را به یک عدد حقیقی غیرمنفی نگاشت می‌کند، که از نظر مفهومی "انرژی ذخیره‌شده" را نشان می‌دهد که می‌تواند برای پرداخت عملیات‌های گران آینده استفاده شود.

هزینه مستهلک عملیات i:
ĉᵢ = cᵢ + Φ(Dᵢ) - Φ(Dᵢ₋₁)

جایی که cᵢ هزینه واقعی است، Dᵢ وضعیت ساختار داده
پس از عملیات i است، و Φ(D₀) = 0 (پتانسیل اولیه)

برای آرایه پویا، یک تابع پتانسیل طبیعی Φ(D) = 2 · (تعداد عناصر) - (ظرفیت آرایه) است، که درست پس از یک تغییر اندازه در صفر می‌ماند و با درج عناصر بیشتر رشد می‌کند، و کاری که برای تغییر اندازه بعدی "پس‌انداز" می‌شود را نشان می‌دهد.

برای یک درج معمولی (بدون تغییر اندازه):
هزینه واقعی cᵢ = 1
پتانسیل 2 واحد افزایش می‌یابد (یک عنصر جدید، فرمول بالا)
ĉᵢ = 1 + 2 = 3

برای یک درج که یک تغییر اندازه از n به 2n فعال می‌کند:
هزینه واقعی cᵢ = n + 1 (کپی n عنصر، به‌علاوه درج جدید)
پتانسیل پیش از تغییر اندازه: 2n - n = n
پتانسیل پس از تغییر اندازه: 2(n+1) - 2n = 2
ĉᵢ = (n+1) + (2 - n) = 3

به‌طور قابل‌توجهی، هر عملیات منفرد، چه معمولی چه فعال‌کننده تغییر اندازه، دقیقاً همان هزینه مستهلک ۳ را تحت این تابع پتانسیل دارد، که کران مستهلک O(1) را با دقت ریاضی تأیید می‌کند، و دقیقاً توضیح می‌دهد چرا هزینه ثابت می‌ماند: تابع پتانسیل دقیقاً "بدهی‌ای" که در طول عملیات‌های گران پرداخت می‌شود را ردیابی می‌کند.

یک مثال دوم: شمارنده باینری

یک شمارنده باینری پیاده‌سازی‌شده به‌عنوان یک آرایه از بیت‌ها را در نظر بگیرید، که با معکوس‌کردن بیت‌ها از موقعیت پایین‌ترین افزایش می‌یابد، و carry ها را در صورت نیاز آبشاری می‌کند. یک افزایش واحد می‌تواند بیت‌های زیادی را معکوس کند اگر یک زنجیره carry طولانی وجود داشته باشد (مانند افزایش ۰۱۱۱ به ۱۰۰۰، که هر چهار بیت را معکوس می‌کند)، که یک هزینه بدترین‌حالت Θ(k) به‌ازای هر افزایش برای یک شمارنده k-بیتی پیشنهاد می‌کند.

با استفاده از روش پتانسیل، Φ(D) را تعریف کن به‌عنوان
تعداد بیت‌های 1 در حال حاضر در شمارنده

برای یک افزایش که t بیت را از 1 به 0
و دقیقاً یک بیت را از 0 به 1 معکوس می‌کند:
هزینه واقعی cᵢ = t + 1
تغییر پتانسیل: -t + 1 (t تا یک صفر می‌شوند، یک صفر یک می‌شود)
ĉᵢ = (t + 1) + (-t + 1) = 2

این نشان می‌دهد هزینه مستهلک به‌ازای هر افزایش یک ثابت O(1) است، صرف‌نظر از اینکه هر زنجیره carry منفرد اتفاقاً چقدر طولانی باشد، چون کاهش تابع پتانسیل دقیقاً هزینه معکوس‌کردن بیت‌های ۱ حمل‌شده را لغو می‌کند.

انتخاب بین سه روش

روش تجمعی:
  - ساده‌ترین برای اعمال، اما فقط هزینه میانگین را اثبات می‌کند
  - نمی‌تواند هزینه‌های مستهلک متفاوتی به انواع عملیات مختلف اختصاص دهد

روش حسابداری:
  - انعطاف‌پذیرتر؛ می‌تواند هزینه‌های مستهلک متفاوتی به‌ازای هر نوع عملیات اختصاص دهد
  - نیازمند یک استدلال "اعتبار" شهودی است، گاهی سخت‌تر برای ساخت

روش پتانسیل:
  - از نظر ریاضی دقیق‌ترین و عمومی‌ترین
  - نیازمند یافتن یک تابع پتانسیل مناسب است،
    که می‌تواند نیازمند بینش باشد اما به‌طور تمیزتری
    به ساختارهای داده پیچیده تعمیم می‌یابد

هر سه روش، وقتی به‌درستی اعمال شوند، دقیقاً همان کران مستهلک را اثبات می‌کنند — آن‌ها لنزهای متفاوتی برای دیدن همان حقیقت ریاضی