對於一個線上計算模型的問題來說，如果我們說每一個操作的均攤時間是 f(n)，那麼對於任意「從頭開始」的 m 個操作來說，花費的總時間不能超過 。感覺有一點像是說，我們允許演算法執行到後期，偶爾會來一次「花大把時間重新整理目前看到的輸入」，但又不影響總時間複雜度。

有些問題，可以透過轉化成線上計算問題，利用線上計算模型的均攤分析，來得出整體的時間複雜度（比方說插入排序、各種自我調整的平衡樹等等）。

一個經典的例子是 C++ 的 vector：我們希望有一種如陣列般支援「O(1) 隨機存取」的資料結構，但同時又能夠有效率地支援 push_back（或 append / extend 等增加能存放資料的陣列大小的操作）和 pop_back（可以縮小陣列大小的操作）。

如果我們在陣列每一次都填滿了資料的情形下，再要求 push_back 一個新的元素的話，此時「跟作業系統索取一個兩倍大的空間，然後把所有人通通搬過去」雖然會是很重的線性時間 O(n) 操作，但是這件事情「在一連串的存取操作過程中」不會常常發生。我們要怎麼嚴謹地說：大概每 n 次才會進行一次 O(n) 的操作呢？這就仰賴均攤分析的幾種常見技巧啦～

常見的分析方法分成兩種：會計方法與勢能函數方法。

會計方法 Accounting Methods

假想我們有一個帳戶，每一次操作都會有人對這個帳戶「存放一些錢（比方說 f(n) 塊錢）」，而演算法進行的每一單位運算都會「花掉帳戶的一塊錢」。如果你能夠證明「這帳戶隨時不會超支」，那麼顯然進行完 m 個操作後，總花費的錢數必定小於 ，也就是說從頭開始完成 m 個操作所花時間不超過 。

勢能函數方法 Potential Methods

對於當前資料結構狀態（必須與操作序列無關）定義一個勢能函數 Φ（或位能函數），這個函數值可能可以是正的或負的。在每一個操作進行完畢後，因為資料結構改變了，所以 Φ 的值也會跟著改變。這個差值，便可用來吸收過多的執行時間，有一點點像是物理中把位能轉換成動能（高位能 → 低位能）然後花費掉了的概念。

明天我們來看看一些能夠用勢能函數方法分析的演算法！