寫給我自己看的資料結構筆記-平攤分析(Amortized Analysis)
上一次我們提到演算法分析，有常數、線性與平方執行時間等等，但有時我們設計的程式直觀上看不出執行時間，又或者是執行時間看起來像常數，但其實是線性等，這時我們可以使用平攤分析法來得到執行時間。
前言
平攤分析法（Amortized Analysis）通常用於分析一個算法的效能，特別是用在動態的資料結構，動態資料結構是一種在運行時可以動態調整大小的結構。這種結構可以根據實際需要動態增加或減少其大小，而不需要事先指定固定大小。
像我們前面提到的 ArrayList 與 LinkedList 就是屬於這種動態資料結構。
平攤分析法會以最壞的情況，對每一次的操作進行分析，將這些操作情況加以平均，來得到平均的操作時間。也因此平攤分析法通常是算出在最壞情況的平均執行時間，並不代表所有情況的平均執行時間。
例子
我們來計算一下在 ArrayList 中，add 的執行時間。
宣告一個 ArrayList，發現裡面還有兩個空間。
接著我們來加入(add)幾個元素：
- 第一次使用 add : 因為還有空間所以直接加入。
- 第二次使用 add : 因為還有空間所以直接加入。
- 第三次使用 add : 因為空間滿了，所以擴大為兩倍空間，然後複製 2 個元素後，再加入一個。現在的長度為 2x2。
- 第四次使用 add : 因為還有空間所以直接加入。
- 第五次使用 add : 因為空間滿了，所以擴大為兩倍空間，然後複製 4 個元素後，再加入一個。現在的長度為 2x2x2。
- 第六次使用 add : 因為還有空間所以直接加入。
- 第七次使用 add : 因為還有空間所以直接加入。
- 第八次使用 add : 因為空間滿了，所以擴大為兩倍空間，然後複製 8 個元素後，再加入一個。現在的長度為 2x2x2x2。
接著我們把這些動作相加起來：
在第四次使用時，我們儲存了4個元素、複製2個。
在第八次使用時，我們儲存了8個元素、複製6個。
在第十六次使用時，我們儲存了16個元素、複製14個。(自己算一下)
也就是說，當我們做 n 次 add，我們會儲存 n 個元素，複製 n-2 個元素，所以總動作的次數是 n+n-2。
為了得到平均動作次數，我們要將總動作次數除以我們執行的次數，也就是 (n+n-2)/n -> (2n-2)/n -> 2-2/n
我們在平攤分析時採用最壞情況，也就是 n 趨近於無限大，那這樣我們的平均動作次數會愈趨近於 2 ，因此 add 為常數執行時間。
這種方式也被稱為聚合分析法（Aggregate Method），將所有結果聚合後計算平均。
可以回憶一下，我們在執行 add 時，不論 ArrayList 多長，執行時間都是差不多的。
另外還有兩種方式，會計分析（Accounting Method）與勢能分析（Potential Method）
後續會介紹到。（其實是因為現在的我看不懂）
結論
平攤分析法用來分析執行時間會有變化的時間複雜度，有些操作會花費極大的時間，但平攤分析會考量到這種情況，將該操作全部做完的總動作次數，除以執行次數來得到平均複雜度。
通常會用在動態的資料結構，例如 ArrayList, HashTable, Binary Tree … 等。
這些架構允許在運行時根據需要動態調整其大小，這使得最壞情況下的平均執行時間成為一個重要的性能指標。
在這種情況下我們則會使用平攤分析法來了解執行時間與時間複雜度。