聚合分析(aggregate analysis)
一個 n 個操作的序列最壞情況下花費的總時間為, 則在最壞情況下, 每個操作的攤還代價為
如棧中的 push, pop 操作都是 , 增加一個新操作
multipop,
def multipop(stk,k):
while not stk.empty() and k>0:
stk.pop()
k-=1
multipop 的時間復(fù)雜度為 min(stk.size,k), 最壞情況為 , 則 n 個包含 push pop multipop 的操作列的最壞情況是
, 并不是這樣, 注意到, 必須棧中有元素, 再 pop, 所以 push 操作與pop 操作(包含 multipop中的pop), 個數(shù)相當, 所以 實際上應(yīng)為
, 每個操作的攤還代價 為
核算法 (accounting method)
對不同操作賦予不同費用 cost (稱為攤還代價 ), 可能多于或者少于其實際代價
當 , 將
(
credit) 存入數(shù)據(jù)結(jié)構(gòu)中的特定對象.. 對于后續(xù) 時, 可以使用這些credit來 支付差額.. 有要求
如棧
| op | ||
|---|---|---|
| push | 2 | 1 |
| pop | 0 | 1 |
| multipop | 0 | min(s,k) |
由核算法, 攤還代價滿足要求, 所以 n 個操作總代價 , 每個操作攤還代價為
勢能法(potential method)
勢能釋放用來支付未來操作的代價, 勢能是整個數(shù)據(jù)結(jié)構(gòu)的, 不是特定對象的(核算法是).
數(shù)據(jù)結(jié)構(gòu) 為初始狀態(tài), 依次 執(zhí)行 n 個操作
進行勢能轉(zhuǎn)換
, 各操作代價為
勢函數(shù) ,
即為
的勢
則第 i 個操作的攤還代價
則
如果定義一個勢函數(shù), 則總攤還代價給出了實際代價的一個上界
可以簡單地以
例如棧操作,
設(shè)空棧為 , 勢函數(shù)定義為棧的元素數(shù)
對于push,
則
對于 multipop,
則
同理 pop 的攤還代價也是0, 則總攤還代價的上界(最壞情況) 為
