標籤

2013年4月19日 星期五

Amortized Analysis簡介

for detail:
http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-nine/

Amortized Analysis
From Wikipedia:
Amortized Analysis finds the average running time per operation over a worst-case sequence of operations. Amortized analysis differs from average-case performance in that probability is not involved; amortized analysis guarantees the time per operation over worst-case performance.

可以想成是把一連串的operation一起考慮它的花費(也就是執行時間)
一起考慮的時候有時候估計比較準確(bound比較緊)
在不考慮機率的情形下，其功能在於:
1. Average performance on a sequence of operations, even some operation is expensive.
得出一連串的operation的平均表現/花費/代價
2. Guarantee average performance of each operation among the sequence in worst case.
保證了將worst case考慮在內，每個operation的平均表現


Aggregated Analysis

T(n): n個operation最差狀況(worst case)下所需花的時間
因此, 每個operation攤分後的所需時間(amortized cost)為T(n)/n

在aggregated analysis中, 我們不區分不同operation的所需時間 
(也就是amortized cost對不同operation都一樣)

example:
Stack的基本動作:
Push(S,x)
Pop(S)
Multipop(S,k)
while not STACK_EMPTY(S) and k>0
POP(S)
k=k-1

使用平常的方法: T(n)=O(n^2)
但是事實上，雖然單一Multipop operation要花很多時間
任何n個連續的operation最多只會花O(n).
因為stack裡面最多只會放n個(n個push後)
而不管是pop或Multipop, 最多真正pop的數目也只會是n
因此總共花的時間不會超過O(n).
T(n)=O(n)
所以平均每個operation所花時間為O(n)/n=O(1)
在aggregated analysis裡面, 我們把每個operation的amortized cost設定為average cost.
在這個例子裡,也就說三種operation的amortized cost都是O(1).

執行一次INCREMENT最多花Θ(k)。即最糟的狀況: 每一位都是1, 全部清成0。
因此執行 n次INCREMENT要花O(nk). T(n) = O(nk).
正確的bound, 但是太鬆!!
所以n個operation的cost應為:

Amortized cost (i.e. Average cost for a sequence of operations):
T(n)/n = O(n)/n=O(1)

The accounting method
“發明”一種給每個operation不同”虛擬cost”的方法。 (用這種方法可能分析T(n)比較容易)
每個operation給不一樣的amortized cost，而每個operation的amortized cost可能比實際的cost少一點或多一點。我們可以把amortized cost > 實際cost想成是存錢 ; 可以把amortized cost < 實際cost想成是花錢。有些operation可能多存一些錢, 供給後面的其他花錢的operation使用

如果我們想要用amortized cost總和來分析T(n)最大有多少, 則必須滿足
這樣的話, 如果是O(f(n))則也是O(f(n))
(i.e.amortized cost 和 實際cost 的成長趨勢一致 )
注意上面的條件是”任何n個operation”都要符合喔!
如果不符合: 則不能保障
”如果是O(f(n))則也是O(f(n))”
(也就是說, 不可以使某個operation多花的錢大於之前存的錢)

Example:
假設我們設定以下的amortized cost:
Push: 2
Pop: 0
Multipop: 0
這樣, push先存下的錢, 足夠讓pop和multipop花嗎?
Pop&Multipop的amortized cost設成0, 因此會花先存下來的錢


Total amortized cost = 2*push operation 數目 = O(n)
因此total actual cost也是O(n)

假設我們這樣定義amortized cost:
設定一個bit為1的時候: 2 ; 其他都是0,
這樣的設計會不會有錢不夠花的狀況?


Total amortized cost=n個INCREMENT設定bit=1的次數
每次最多只設定一個bit為1
因此n次最多設定n個bit為1
Total amortized cost=O(n)
Total actual cost=O(n)

The potential method
比較:
Accounting method是使用”先存後花”的方式。
Potential method則是用potential來計算”之前的operation使目前的資料結構有殘存多少能量”。
物理定義:Potential energy is the energy stored in a body or in a system due to its position in a force field or due to its configuration*

(未完待續)



Complexity revision:
若是我們說一個演算法的複雜度函數 f(n) ∈ Ο(g(n))，就代表函數 f(n) 的成長趨勢與 g(n) 相似或是更慢的。
為了方便比較，我們可以將 f(n) 與 g(n) 比擬成 a 跟 b，則：
  • f(n) ∈ Ο(g(n)) ≈ a ≤ b
  • f(n) ∈ Ω(g(n)) ≈ a ≥ b
  • f(n) ∈ Θ(g(n)) ≈ a = b
  • f(n) ∈ ο(g(n)) ≈ a < b
  • f(n) ∈ ω(g(n)) ≈ a > b

1.O(1)或O(c)：稱為常數時間(constant time)
　　這表示演算法則的執行時間是一個常數倍，而忽略資料集合大小的變化。如果有這樣的演算法則存在，則我們可以在任何大小的資料集合中自由的使用，而不需要擔心時間或運算的次數會一直成長或變得很高。
2. O(n)：稱為線性時間(linear time)
　　它執行的時間會隨資料集合的大小而線性成長。我們可以找到一個例子是在一個沒有排列過的資料集中要找一個最大元素，且我們以簡單的方式去解釋其內容，直到我們將所有的資料都找過並且找到最大值為止。
3.O(log2n)：稱為次線性時間(sub-linear time)
這一種函式的成長速度比線性的程序還慢，而此常數(它是不成長的)的情形還快。
4.O(n2)：稱為平方時間(quadratic time)
演算法則執行時間會成二次方的成長，這種會變得不切實際，特別是當資料集合的大小變得很大時。
5.O(n3)：稱為立方時間(cubic time)
6.O(2n)：稱為指數時間(exponential time)
7.O(n1og2n)：介於線性及二次方成長的中間之行為模式。

O(1) 與Amortized O(1)的分別:
張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)