效能分析與複雜度

效能分析與複雜度 ( Performance Analysis & Complexity )

演算法的目的在於改善一個東西或問題，並在從問題中找出現有最好的辦法

一個好的演算法可以節省許多時間與記憶體空間，而一個程式在執行時所佔用的記憶體空間也會反映出執行所需要的時間

因此才需要效能分析 ( Performance Analysis ) ，但其實也不用要求的非常精準，只需要一個最後結果可符合需求且大家都能夠接受的就行了

效能分析 ( Performance Analysis )

因為每一隻程式在不同硬體設備上執行所花的時間都不同，但演算法不是只適用於一台特定的硬體設備

因此分析方法必須是不受電腦設備、程式語言、程式設計者，以及實作上的細節影響

但我們可以從這個分析結論得知這個演算法效率如何

其中分析方法就是 Complexity Theory，也是目前比較普遍的方法

複雜度理論 ( Complexity Theory )

在 Complexity Theory 中，分成 時間複雜度(Time Complexity) 與 空間複雜度(Space Complexity)

一般 Complexity 表示使用漸近式符號 ( Asymptotic Notation )

目的是為了表現時間或空間函數的成長趨勢，種類有：

Big-oh：O
Omega：Ω
Theta：Θ
little-oh：o
little-omega：ω

以及常見的複雜度 groth rate 等級 ( 由小到大 )：

小到大
小	常數 (constant) 時間	Ｏ(1)
↓	雙重對數 (doubly log) 時間	Ｏ(log log n)
↓	對數 (log) 時間	Ｏ(log n)
↓	線性 (linear) 時間	Ｏ(n)
↓	n log n 時間	Ｏ(n log n)
↓	多項式 (polynomial) 時間	$Ｏ$
↓	指數 (exponential) 時間	$Ｏ$
大	階層 (Factorial) 時間	Ｏ(n!)

圖片來源

漸近式符號定義 ( Asymptotic Notation Definition)

☆ Big-oh：O

$：存在兩個正整數，$ ，滿足 f(n) ≤ C·g(n)，Ɐ n ≥ n_0$

Big-oh 描述函式的上界 ( upper-bound )

$例：，則$

$因為可以找到兩個正常數，，$ $使， Ɐ$ $，取$ $，所以$

☆ Omega：Ω

$：存在兩個正整數，$ ，滿足 f(n) ≥ C·g(n)，Ɐ n ≥ n_0$

Omega 描述函式的下界 ( lower-bound )

$例：，則$

$因為可以找到兩個正常數，，$ $使$ $，所以$

☆ Theta：Θ

$：存在兩個正整數，$ ，滿足 C_1·g(n) ≤ f(n) ≤ C_2·g(n)，Ɐ n ≥ n_0$

Theta 描述函式的邊界 ( bound )

$例：，$

$因為可以找到個正常數，，，$ $使， Ɐ$ $取，，$ $取，，$ ，(n-9)(n+1) ≥ 0，n ≥ 9$

little-oh：o

$：對於所有正整數存在一個，使得， Ɐ$

例1：f(n) = 5n = o(n)

5n < C·n，Ɐ C 皆要成立但 C = 5，5n ≮ 5n ⇒ False

$例：$ True

little-omega：ω

$：對於所有正整數存在一個，使得， Ɐ$

例1：f(n) = 5n = ω(n)

因為 5n > C·n，Ɐ C 取 C = 5 ⇒ 5n ≯ 5n ⇒ False

$例：$ True

遞迴時間函式 (Recursion Time Function)

一般求解 Recursion Time Function 常見做法有幾種：

(1) 迭代法

(2) Master Theorem / Extended Master Theorem

求解 Recursion Time Function 還可以用 Recursion Tree 的作法來猜測近似解

迭代法

例1：T(n) = 2T(n-1)+1，T(1)=1，求T(n)=？ O(?)

T(n) = 2T(n-1)+1

= 2T(n-1)+1

= 4T(n-1)+1+2

= 4[2T(n-3)+1]+1+2

= 8T(n-3)+1+2+4

= …

$，$

例2：T(n) = T(n-1)+n，T(0)=0，求T(n)=？ O(?)

T(n) = T(n-1)+n

= T(n-2)+(n-1)+n

= T(n-3)+(n-2)+(n-1)+n

= …

= T(n-n)+n+n-1+…+1

= T(0)+((n+1)n)/2

$，$

Master Theorem

在演算法中稱 主定理，若 T(n) = aT(n/b)+f(n)，其中 a ≥ 1，b ≥ 1，f(n) 是正成長函式，則可以使用 Master Theorem 來計算決定 T(n) = Θ(?)

使用方法：

Step 1.　 $先求出$

Step 2.　 $與比較，分成個：$

$：若，為之正常數，則$
$：若，則$
$：若，為之正常數$ ，且 af(n/b) ≤ C·f(n)，C 為 < 1 之正常數，則 T(n) = Θ(f(n))$

通常大多問題帶這個 Master Theorem 公式就可以直接求解，神一般好用，但切記別用得太爽www，有些情況下會誤用，如下

例：T(n)=2T(n/2)+nlogn

【誤用示範】

a=2，b=2，f(n)=nlogn

$而$ n^(log_ba) = n^1 = n$

Case 3 ⇒ T(n) = Θ(f(n)) = Θ(nlogn) = O(nlogn)

原因：

$，為正常數$

$，為正常數，但找不到$

$，常數$

所以無法使用

$正解：．$

效能分析與複雜度

效能分析 ( Performance Analysis )

複雜度理論 ( Complexity Theory )

漸近式符號定義 ( Asymptotic Notation Definition)

☆ Big-oh：O

：存在兩個正整數，，滿足 f(n) ≤ C·g(n)，Ɐ n ≥ n_0$

☆ Omega：Ω

：存在兩個正整數，，滿足 f(n) ≥ C·g(n)，Ɐ n ≥ n_0$

☆ Theta：Θ

：存在兩個正整數，，滿足 C_1·g(n) ≤ f(n) ≤ C_2·g(n)，Ɐ n ≥ n_0$

little-oh：o

：對於所有正整數存在一個，使得，Ɐ

little-omega：ω

：對於所有正整數存在一個，使得，Ɐ

遞迴時間函式 (Recursion Time Function)

迭代法

Master Theorem

以上皆為自己整理的筆記，僅供參考與複習使用。

$：存在兩個正整數，$ ，滿足 f(n) ≤ C·g(n)，Ɐ n ≥ n_0$

$：存在兩個正整數，$ ，滿足 f(n) ≥ C·g(n)，Ɐ n ≥ n_0$

$：存在兩個正整數，$ ，滿足 C_1·g(n) ≤ f(n) ≤ C_2·g(n)，Ɐ n ≥ n_0$

$：對於所有正整數存在一個，使得， Ɐ$

$：對於所有正整數存在一個，使得， Ɐ$