Amortized Analysis
অ্যামর্টাইজড বিশ্লেষণ
একটা দামি operation-এর খরচ পুরো sequence-এ ছড়িয়ে দেখা — worst case এক call-এ খারাপ হলেও গড়ে প্রতি operation সস্তা থাকে।
also: amortized cost
Amortized analysis প্রশ্ন করে: n বার চালালে মোট খরচ কত, গড়ে প্রতি operation-এ কত? মাঝে মাঝে একটা দামি operation হলেও বাকিদের সস্ততা সেই খরচ ঢেকে দিতে পারে।
| পদ্ধতি | ভাবনা |
|---|---|
| Aggregate | পুরো sequence-এর মোট খরচ ÷ n |
| Accounting | সস্তা operation-এ ক্রেডিট জমা রেখে দামিটা বাঁঝা |
| Potential | structure-এর state-এর উপর potential function বসানো |
ক্লাসিক উদাহরণ — dynamic array-র append:
সাধারণ append: O(1)
capacity শেষে resize: O(n)
amortized append: O(1)Doubling growth-এ মোট copy-র সংখ্যা n-এর চেয়ে কম — তাই গড়ে constant।
সাবধান: amortized bound আর average case এক জিনিস নয়। এখানে কোনো input distribution নেই — যেকোনো valid sequence-এর উপর guarantee খাটে।