均攤分析

簡介

#

均攤分析 (Amortized Analysis) 是一種分析演算法時間複雜度的方法，它不是對每次操作的時間複雜度進行分析，而是對一系列操作的時間複雜度進行分析。

基本思想是，對於一系列的操作，有些操作可能需要花費較多的時間，但是這些操作不會每次都發生，而是在某些情況下才會發生，而這些情況發生的次數受到某些限制，因此可以將這些操作的時間分攤到其他操作上。

例子

#

考慮以下程式碼：

vector<int> vec;

for (int i = 1; i <= n; i++) {
    vec.push_back(a[i]);
    while (vec.size() && vec.back() < a[i]) {
        vec.pop_back();
    }
}

如果已經很熟悉前面章節講的時間複雜度分析的話，也許你會直覺的認為這個程式碼的時間複雜度是 \(O(n^2)\)，因為 push_back 和 pop_back 都是 \(O(1)\) 的操作，而「最壞情況」下，pop_back 可能會執行 \(O(n)\) 次。

但是，如果我們仔細觀察這個程式碼，我們會發現，pop_back 的次數是有限的，因為每次 pop_back 之後，vec 的大小都會減少 1，而且 vec 的大小不會變成負數，因此 pop_back 的次數不會超過 \(n\) 次。

即便某些情況下，pop_back 可能一次就執行了 \(n\) 次，但是這種情況不會每次都發生，而是在某些情況下才會發生，因此可以將這些操作的時間分攤到其他操作上。

因此，這個程式碼的時間複雜度實際上是 \(O(n)\)，而不是 \(O(n^2)\)。