大神的世界

效能評估依照是否與機器相關（machine dependent）可分為二類

1. Performance analyse: machine independent

2. Performance measurement: machine dependent

machine dependent 的測試方式為 ： run 一支程式，並計算執行時間

此方法想當然而和電腦的設備密切相關

如果電腦的 CPU 夠多，memory夠大，測出來的時間就會愈短，代表效能愈好

這樣顯得跟程式關係不大，因為好的效能來自好的電腦

因此，在測試程式效能時，必須跳脫這個框架

接著，我們來討論 Performance Analyse ，此評估方式與電腦設備無關

使用的方法為複雜理論（complexity theory）

其中，較常用的有 Space complexity(空間複雜度) 和 Time complexity (時間複雜度）

Space complexity

定義： 一個演算法在運行過程中臨時佔用的 memory 大小（量度）

公式： S(P) = c + Sp(I)

S(P) :  程式所佔用的空間

c     : 演算法本身所佔用的空間  （constant）

Sp(i) : 演算法在運行過程中會佔用的臨時空間（e.g. parameter 、 local variable etc.），包含 I/O 所需的儲存空間

Sp(I) 會直接影響 S(P)， 因為 c 是個 constant

 

Time complexity

定義： 一個演算法所需的運行時間（定量）

公式： T(P) = c + Tp(I)

T(P) : 運行此 program 所花費的時間

c     : compile 所需要的時間

Tp(I) : 執行演算法所花費的時間，跟演算法及輸入有關

準確的時間複雜度計算與指令集有關，因為不同的敘述（statements）會對應到不同的指令（instructions）

其中，不同的指令又會有各自所需的 clock cycle

因此若要準確計算程式運行的時間，必須從組合語言下手

註：

statement： 高階語言的一行指令

instruction: 組合語言的一行指令

這裡，我們先忽略複雜的運算，只討論運行時共需幾道指令（為方便敘述，此處"指令"泛指高階及低階語言）

第1種計算方法 : 在指令後面加上 count++ 來計算共有幾道指令

需要特別注意

for 迴圈之後也要執行 count++ ，因為i++也是一道指令

此外，變數宣告沒有 assign 的話，不當作一條指令，因為編譯成組合語言，不存在該指令

以上圖為例，float sum() 共運行 2n+3條指令

當 n >> 1時，我們可忽略常數項不計

 

第2種計算方法 ： 建表

將每一道指令紀錄在表中，並紀錄該道指令所需的 step 及出現的 frequency

把這二個數字相乘，可得到該指令在運行演算法過程中執行的次數

接著，把這些數字加總,可得此演算法所需的總指令數

 

最後，時間複雜度共可分成三種case

1. Best case

2. Worst case

3. Average case

若以排序小到大來說

Best case: 輸入數列恰好小到大排序

Worst case: 輸入數列恰好大到小排序

Average case: 輸入數列為任意排序

常見的時間複雜度表示法有 O（big-O) 、 Θ (big-Theta) 、Ω (big-Omega)

 

O（big-O)

定義： 存在正數 c 和 n0 使得 f(n) <= cg(n) for n >= n0， 則 f(n) = O(g(n))

f(n)： 運行演算法所執行的總指令數

g(n)： n 的函數，常用的有 1（常數型）、n^k (多項式型）、log n (對數型）  等

此外，g(n) 必須是最小 upper bound

否則可能性有無限多種

 

例如說：

f(n) = 3n+2

我們取 g(n) = n , c = 4, n0 = 2

=>  3n + 2 <= 4n  for n >= 2 則 3n+2 = O(n)

 

 

Ω (big-Omega)

定義： 存在正數 c 和 n0 使得 f(n) >= cg(n) for n >= n0， 則 f(n) = Ω(g(n))

此外，g(n) 必須是最大 lower bound

 

例如說：

f(n) = 3n+2

我們取 g(n) = n , c = 3, n0 = 1

=>  3n + 2 >= 3n  for n >= 1 則 3n+2 = Ω(n)

 

 

Θ (big-Theta)

定義： 存在正數 c1、c2 和 n0 使得 c1 g(n) <= f(n) <= c2 g(n) for n >= n0， 則 f(n) = Θ(g(n))

此外，g(n) 必須同時是最小 upper bound 和 最大 lower bound

 

例如說：

f(n) = 3n+2

我們取 g(n) = n , c1 = 3, c2 = 4, n0 = 2

=>  3n <= 3n + 2 <= 4n  for n >= 1 則 3n+2 = Θ(n)

 

 

此外，之所以 for n >= n0 是因為我們假設n會非常大