تحلیل سرشکن (amortized analysis)

اینجا هدف این است که هزینه‌ی یک عمل را بدون توجه به ورودی به دست بیاوریم. مثلاً اگر یک شمارنده بیتی داشته باشیم، هزینه‌ی هر بار زیاد کردنش میشه هزینه‌ی شمردن تا عددی که الآن توی شمارنده هست:

ولی اگر بخواهیم مستقل از مقدار فعلی شمارنده به دست بیاوریم، زمانش O(1) می‌شود.

روش‌های تحلیل سرشکن:

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

روش حسابداری (accounting): یک مخزن پول (تعداد اعمال) داریم و برای هر عمل یک هزینه داریم.

روش تابع پتانسیل (potential function): یک تابع پتانسیل تعریف می‌کنیم و هزینه‌ی هر عمل را به صورت cost+pot(i)-pot(i-1) تعریف می‌کنیم.

... (اینترنت قطع بود خودم تنهایی خوندم! منبع اسلایدهای الگوریتم پیشرفته)