有三種分析方法：
Aggregate Analysis
Accounting Method
Potential Method
Aggregate Analysis(總量分析)
分析一連串的operations，討論最壞情形
//因為單一operation可能很花時間，平均而言每個花的不多
Example 1. Stack Operations
Push(S, x)：把x放到S裡
Pop(S)：拿出S最上面的
MultiPop(S, k)：從S裡面拿k個
第一種看法：
Push、Pop都是花O(1)
MulitPop最慘要花O(n)//一次拿n個
總共n個operations -> n*O(n) = O(n²)
平均一個operation -> O(n)
第二種看法：
放進去之後，只會拿出來一次
Pop + MultiPop 的次數≤n
Push 的次數≤n
Push + Pop + MultiPop的次數≤2n
總共n個operations -> O(n)
平均一個operation -> O(1)
Example 2. Incrementing a Binary Counter
二進位的計數器，用一個陣列A來記
第一種看法：
一個operation最差會需要O(k)
總共n個operations -> n*O(k) = O(nk)
平均一個operation -> O(k)
第二種看法：
第0位，每1次要翻轉
第1位，每2次要翻轉
第2位，每4次要翻轉
…//翻轉是指，從0變1 或 從1變0
總共n個operations -> n + floor(n/2) + floor(n/4) +… ≤2n
平均一個operation -> O(1)
Accounting Method
每個物件都有自己的帳戶
讓每個operation有不同的cost
//在Aggregate Analysis每個cost相同
//有時比實際多，有時比實際少
amortized cost：付的所有cost
credit：多付的cost
ci：第i個動作真正的cost
c^i：第I個動作付的cost
Example 1. Stack Operations
Push：$1是為了放進去，$1是為了拿出來
total cost ≤ amortized cost ≤ 2n
平均一個operation：O(1)
Example 2. Incrementing a Binary Counter
設定一個bit，從0->1 花 $2
$1 用在set，$1 留著翻轉
total cost ≤ amortized cost ≤ 2n
平均一個operation：O(1)
Potential Method
所有物件共用一個帳戶
困難的是要決定potential function
Di：經過i個operation後，帳戶的錢
D0：帳戶的初始值
ci：第i個動作真正的cost
c^i：第i個動作付的cost
Potential function：題目會給
要付的 = 真正花的 ＋ 帳戶增加的
流程：
step1. 確定potential function
step2. 確定存款比一開始多
step3. 將c^i相加
step4. 全部交的≥全部花的
->可知平均而言的花費
Example 1. Stack Operations
Potential function：在stack中有幾個物件
全部的operations -> O(n) //所有c^i加總
平均一個operation -> O(1)
Example 2. Incrementing a Binary Counter
Potential function：1的個數(bi)
假設第i個operation是把ti個1設成0
//除了把1設成0，還要把0設成1
//ex. 0111 -> 1000 或 1111->0000(溢位)
bi ≤ b(i-1)-ti + 1
全部的operations -> O(n)
平均一個operation -> O(1)
Dynamic Tables
想像成是學生在教室上課
若教室滿了換一個兩倍大的，然後把學生搬過去
若使用率低於1/4，換一個只有一半大的教室
α(T)：負載率 = num[T]/size[T]
用potential method來分析：
當α(T)≥1/2時，potential_function(T)=2 ∙ num[T] − size[T]
當α(T)<1/2時，potential_function(T)=size[T]/2 − num[T]
insert又分成三種case
case1. insert前α(T)≥1/2，insert後α(T)≥1/2
case2. insert前α(T)<1/2，insert後α(T)<1/2（沒換教室）
case3. insert前α(T)<1/2，insert後α(T)≥1/2（沒換教室）
delete又分成
case1. delete前α(T)<1/2
1a. 沒有縮小教室
1b. 有縮小教室
case2. delete前α(T)≥1/2
2a. delete後，α(T)≥1/2
2b. delete後，α(T)<1/2
看圖應該會比較好懂
結論：一次 insert 需花O(3)
一次 delete 需花O(2)
n個operations 需花O(n)
