Algorithm :: Amortized Analysus (Unfinish)

在分析時間複雜度的時候，總是使用worst case (big-O)有時候會不夠緊 (over-estimate time)
分析實際狀況比較符合我們的需求

Three method:
(1) Aggregate method
    Like brute force, calculate n sequence operation = T(n). T(n)/n is the average cost of each operation
(2) Account method
    Define a actually cost for every operation. Take extra cost for future usage
(3) Potential method
    Similar with (2). Define a potential function to record

Example_1: An algorithm composed of 3 operations:
push(S, x); // push element x into stack S
pop();         // pop one element
multi-pop(S, k); // pop k element from stack S

  Consider n sequence operations. the normal analysis is: worst case of each operation is O(n) (every operation is multi-pop(S, n)).
  By amortize method(1):
    Since maximal number of element to push into S is n, so the maximal sum number of k using in multi-pop(S, k) is also k. O(n) in n operations. The average cost for each operation is O(1)
  By amortize method(2):

  By amortize method(3):

Example_1

  Consider n sequence operations. the normal analysis is
  By amortize method(1):

  By amortize method(2):

  By amortize method(3):

Example_2

Example_3
把考試題目放上來

Reference:
[1] Mr. opengate
http://mropengate.blogspot.com/2015/06/algorithm-amortized-analysis.html
[2] CSDN
https://blog.csdn.net/touzani/article/details/1696399