如何理解演算法平攤分析中的勢能方法（Potential Method）？
最近結合MIT演算法公開課和演算法導論學習演算法，在平攤分析這一課中的勢能方法（Potential Method）存在以下幾點疑惑：
1. 根據^c_i = c_i + P_i - P_i-1，我們目標是求得平攤後的時間^c_i，那首先要確定c_i範圍，那既然已知c_i，為何不用聚集方法直接求得平攤時間？換言之，勢能方法有何優勢，在何種情況下相對聚集方法和記賬方法而言更適用？2. 對於一個演算法，如何確保數據結構的狀態（state of data structure）正確投影（map）到了勢能函數（Potential Function）上？換言之，如何確保勢能函數的正確性？例如：對於Stack這種數據結構，勢能函數可以是f(state) = k, k為當前Stack上的元素總數（忽略了k前面的常數係數）。我們如何確保該函數的正確性（經指正：此處表述為「準確性」更好），也就是為何我們可以把Stack上的元素數量作為函數值？感激不盡
演算法不是純數學
要從更「歡脫」的思路來理解，我就是一直這麼做的（比如，紅黑樹是一個想要減肥的胖子）不要為符號與概念所累為什麼我們需要均攤分析（Amortized Analysis）？
因為Big O跟病毒一樣具有傳染性。大多數時候，需要O的傳染性來簡化情況，避免陷入到無盡的常數和低階運算中去，得到更純粹的解按演算法導論書本的例子
對於一個Stack操作，POP和PUSH都是O(1)的，這很好理解現在定義了一個新的操作，Multi-POP，表示POP n個元素，顯然這是一個O(n)的操作
好了，如果我們進行一連串隨機的POP PUSH Multi-POP，那麼上界是多少？根據O的傳染性，O(n) &> O(1)，那麼單個操作，我們全都按O(n)算，有n個操作，那就是O(n^2)。
有錯嗎？沒有。但直覺告訴你，肯定哪裡有什麼不對！怎麼可能存在一個Stack，你可以一直Multi-POP下去？第一次Multi-POP(n)之後，Stack就已經清空了。這3種操作不是平行的，而是互相影響的。換言之，你每次的PUSH創造「機會」給POP和Multi-POP。POP和Multi-POP才能「消費」著這些機會，不存在無限制的消費。這是一個被污染的結果，我們需要工具來對抗Big O的傳染性。
書中介紹了兩種方法1. Accounting Method2. Potential Method兩種方法的內核基礎是一樣的（各個操作是相關的），不同是角度。
Accounting Method，要求你先計算出每個操作要「存」多少錢，然後給別的操作消費。
Stack的每次PUSH都花2元，1元是支付自身的操作，還有1元存起來。接下來任意的POP和Multi-POP就不用花錢了，因為PUSH操作已經付過了。這樣上界就被我們進一步限制到了O(2n) = O(n)現在是重頭戲，勢能方法
這種方法是漸進的，你一開始並不需要知道究竟要存多少錢。想像一下你正在坐過山車，現在車正在爬坡
再也不用管究竟要存多少錢，要花多少錢了。你只需要證明，每個操作積累的勢能是常數的，別的操作只是消費勢能就好了，從當一個Accountant的工作中解放出來。
回到Stack的例子
每次的PUSH，Stack的長度都加1，這就好像過山車在爬坡，積累1個勢能單位，讓其能夠在後續的POP和Multi-POP回歸到長度為0的狀態。無論Stack有多長，我們都有足夠的勢能單位，讓Stack回歸到0。
能理會到跟Accounting Method的差異沒？如果有看書的童鞋，還可以看到有個計數器的例子，用勢能方法也很容易說明。我們先定義，每翻出一個1，那麼就是勢能狀態改變了，需要積累1個勢能單位將其變為0的原始值。
每次計數器加1，實際消耗為翻掉1的數量加上1，狀態的變化為增加了1個勢能單位，但又消費掉了翻掉1的數量的勢能單位，對消一下，得到2。這是一個常數操作。
這個例子中的加1操作，既是勢能生產者，又是勢能消費者。
演算法分析條條大路通羅馬，即使你不用以上方法，用數列極限一樣可以算得出來。
菜雞謝邀
忍不住了大半夜的我先馬一下...
幫你艾特大神..第二次編輯
————————————樓上@林誠 先生指導了下記賬和勢能兩者等價，在複雜情況下勢能法更加便捷。為了避免一知半解的答案誤人子弟，還請看別的答案。
_______________________________
講真從來沒用過攤還分析，一知半解權作討論
用算導的例子。一個表在插入刪除操作中進行擴張和收縮。
核演算法(記賬)和勢能法的區別在於前者對數據結構中每一操作系列進行記賬，後者是對整體數據結構。
如例,在裝載因子的四種情況中，(不)觸發擴張(收縮)，第i次操作的攤還代價為 0 /1/ 2/3
定義勢函數後比較容易求出來換核演算法 因為這裡涉及的比較多的操作 它的攤還代價我不知道怎麼寫
聚合分析求最壞情況下的每個操作的攤還代價。同樓上所言不夠靈活。
複雜的情況，勢能法相比而言比較好用。
大概可以解決第一個問題。第二個討論定義勢能函數
勢能不為負值，保證勢函數定義的操作序列總攤還代價為總實際代價的上界。米有了...不知道對不對歡迎指正和討論...在普通的核演算法中每個操作的攤還代價都是猜出來的，所以你需要挨個試才能得出攤還代價才行。
所以需要一個好的方法來計算出每個操作的攤還代價，勢能法就是做這件事的。
勢能法無法理解，你不需要理解，它只是一個獲得某個操作攤還代價的方法而已。
比如Stack的例子：
^c_i = c_i + P_i - P_i-1，攤還代價等於實際代價加上勢能差，這裡的勢能表示stack中元素個數，代價表示時間，這個相加表示什麼呢？這個就很難讓人理解。其實它什麼都不表示。所以它僅僅是一個獲得某個操作攤還代價的方法而已。
然後把這些攤還代價代入到核演算法中，就計算出來總的攤還代價。
謝邀，我沒上過正式的演算法分析課，不過搞OI的時候接觸過一些均攤分析，當時看了陳胤伯（delayyy）的課件，他說：
?把勢函數想像成一種「存儲」，在不怎麼耗時的時候存下，在非常耗時的時候取出來。
?類似於錢，只要「自己掏的錢」和「挪用的存款」不超過某個界，那麼花的錢一定不超過那個界。
我覺得均攤分析主要是估計各種操作出現的頻率，聚集方法相對死板（但其實很好用……）。
隱隱覺得記賬和勢能沒大差別，但是勢能法靈活點？……最後，所謂正確性更應該說是準確性吧……基本思想如delayyy語：?在一個很快的操作時稍微增加一點
?在一個耗時的操作時急劇減少
我看了 @林誠 的解釋後感覺領悟不少，我來分享下我的理解吧，著重回答第二個問題 @西行寺·幽幽子 。
1. 根據^c_i = c_i + P_i - P_i-1，我們目標是求得平攤後的時間^c_i，那首先要確定c_i範圍，那既然已知c_i，為何不用聚集方法直接求得平攤時間？
換言之，勢能方法有何優勢，在何種情況下相對聚集方法和記賬方法而言更適用？
答：當 c_i 不固定的時候直接用 c_i 求是不靠譜的，根據演算法導論上的例子，棧的 Multi-POP 操作表面上複雜度是 O(彈出的元素個數) 但實際上當棧的剩餘元素不夠時，這個複雜度是不成立的。而勢能分析可以把變化累積，最後在進行分析。一個比喻：
1 = 1/3 + 1/3 + 1/3 （勢能分析，沒有丟失精度）
1 != 0.33 + 0.33 + 0.33 （其他分析，丟失精度）
2. 對於一個演算法，如何確保數據結構的狀態（state of data structure）正確投影（map）到了勢能函數（Potential
Function）上？換言之，如何確保勢能函數的正確性？例如：對於Stack這種數據結構，勢能函數可以是f(state) = k,
k為當前Stack上的元素總數（忽略了k前面的常數係數）。我們如何確保該函數的正確性（經指正：此處表述為「準確性」更好），也就是為何我們可以把Stack上的元素數量作為函數值？
答：數據結構的各種性質都可以投影到勢能函數上，其實勢能函數的選取是非常任意的，當然你可以選一些很離譜的勢能函數（比如說恆等於1），但是這樣就對分析沒有任何意義，我們要選取一些比較好的勢能函數（通過觀察操作對數據結構的改變找出平衡各個操作的勢能函數，以及一些靈感，算導中的動態表是一個好例子）。。下面可以分析下為何任取勢能函數都是可以的。對於 c_i 我們在其周圍添加一些符號，讓其看起來像這個樣子：
^c_i = c_i + P_i - P_i-1
對於任意的 i 這個等式是沒有問題的，但是整個等式中只有一項是有確切意義的，那就是 c_i，但當我們給 P_i，..P_i - 1 賦予比較好的意義，那門整個等式就有意義了。而這個比較好的意義要保證的最最重要的一件事，那就是保證不論 i 是何種操作，以及對任意的 i，通過計算得到的 ^c_i 都是一個常數。然後我們一求和：
^c_0 + ^c_1 + ... + ^c_n = c_0 + c_1 + ... + c_n + P_n - P_0
算出了 ^c_i 的加和以及P_n, P_0的話 c_i 的和就出來了。
所以關鍵就是給 P_0, P_1, ... P_i 賦予一個意義，我們令 P_i 表示第 i 次操作後的棧長，這樣我們就能夠計算 ^c_i 了，怎麼算，看算導去。。
如何才能使得 P_0，P_1...P_n 映射到一個值呢。。給他一個關聯 i （i 關聯著操作）的函數。比如算導中，我們就令 P_i 表示第 i 次操作後的棧長，那就完美解決了所有問題。。當然有個小尾巴，那就是求和後還有 P_n 和 P_0。只要我們確保這兩個值落在一個合理的範圍那就OK了，比如對於算導的例子而言，P_0一定是 0， 0 =&< P_n &<= n。
看完這裡之後，就可以接著看看算導上動態表的例子，用那個例子告訴你選取勢能函數的要點。
推薦閱讀：
※實現group by最好的辦法？
※學習演算法與數據結構，有什麼比較好的mooc推薦么，還有比較好的書籍推薦？
※如何看待Thomas Cormen所說看完《演算法導論》需要的時間 ？
※如何通俗地解釋「置信區間」和「置信水平」？