第 1 章 演算法分析.

Presentation on theme: "第 1 章 演算法分析."— Presentation transcript:

1 第 1 章 演算法分析

2 目次 1.1 演算法 1.2 Big-O 1.3 動動腦時間 1.4 練習題解答

3 1.1 演算法 演算法(Algorithms)？ 程式效率分析方式(performance analysis)
1.1 演算法 演算法(Algorithms)？ 是一解決問題(problems)的有限步驟程序 產生解答中一步一步的程序 程式效率分析方式(performance analysis) 時間複雜度分析(time complexity analysis) 空間複雜度分析(space complexity analysis)

4 1.1 演算法(con.t) 時間複雜度分析步驟 Ex：四個範例 求出程式中每一敘述的執行次數( ‘{‘ 和 ’}’ 不計算)
再將這些執行次數加總 求出程式之Big-O，即為該程式之時間複雜度 Ex：四個範例

5 1.1.1 陣列元素相加 執 行 次 數 int sum(int arr[], int n) { int i, total=0; 1
陣列元素相加 　　 執 行 次 數 int sum(int arr[], int n) { int i, total=0; for (i=0; i<n; i++) n+1 total+=arr[i]; n return total; } 2n+2

6 矩陣相加 執 行 次 數 void add (int a[][], int b[][], int c[][], int m, int n) { for (int i=0; i < n; i++) n+1 for (int j=0; j < n; j++) n(n+1) c[i][j] = a[i][j] + b[i][j] n2 } 2n2+2n+1

7 1.1.3 矩陣相乘 執 行 次 數 void mul(int a[][], int b[][], int c[][], int n) {
矩陣相乘 執 行 次 數 void mul(int a[][], int b[][], int c[][], int n) { int i, j, k, sum; for (i = 0; i < n; i++) n+1 for (j = 0; j < n; j++ ){ n(n+1) sum = 0; n2 for ( k = 0; k < n; k++ ) n2(n+1) sum = sum + a[i][k] * b[k][j]; n3 c[i][j] = sum; n2 } } n3+4n2+2n+2

8 1.1.4 循序搜尋 執 行 次 數 int search(int data[],int target, int n) { int i; 1
循序搜尋 　　 執 行 次 數 int search(int data[],int target, int n) { 　 int i; 　1 for (i = 0; i < n; i++) n+1 if (target == data[i]) n return i; } 2n+3

9 1.2 Big-O 程式或演算法執行時間的計算 Big-O定義 ∑ (每一敘述的執行次數 * 執行該敘述所需的時間)
通常只考慮執行的次數 Big-O定義 f(n)=O(g(n))，若且唯若存在一正整數c及n0，使得f(n)≦cg(n)，對所有的n，n≧n0 此時，f(n)的Big-O為g(n)

10 1.2 Big-O (con.t) Big-O範例 由上述範例可知，Big-O只要取其多項式最高次方的項目即可 3n+2=O(n)
∵當c=4，n0=2，3n+2 ≦4n ∴ 3n+2 的 Big-O 為 n l0n2+5n+1=O(n2) ∵當c=11，n0=6，10n2+5n+1 ≦11n2 ∴ l0n2+5n+1 的 Big-O 為 n2 由上述範例可知，Big-O只要取其多項式最高次方的項目即可

11 1.2 Big-O (con.t) 常見的Big-O類型 O(1) 稱為常數時間 (constant) ← 效率最好，執行時間最少
O(log n) 稱為對數時間 (logarithmic) O(n) 稱為線性時間 (linear) O(n log n) 稱為對數線性時間 (log linear) O(n2) 稱為平方時間 (quadratic) O(n3) 稱為立方時間 (cubic) O(2n) 稱為指數時間 (exponential) O(n!) 稱為階層時間 （factorial） O(nn) 稱為n的n次方時間 ← 效率最差，執行時間最長

12 1.2 Big-O (con.t)  的定義 f(n) = (g(n)),若且唯若，存在正整數c和n0，使得f(n)≧cg(n)，對所有的 n，n≧n0 範例 3n+2=(n) ∵當c=3，n0=1，3n+2≧3n ∴ 3n+2 的  為 n

13 1.2 Big-O (con.t)  的定義 f(n)=  (g(n)),若且唯若，存在正整數c1，c2及n，使得c1*g(n)≦f(n)≦c2*g(n)，對所有的n，n≧n0 範例 3n+1= (n) ∵當 c1=3，c2=4，且n0=2，3n≦ 3n+1 ≦4n ∴ 3n+1 的  為 n

14 1.2 Big-O (con.t) Big-O, ,  的表示情形
3log(n)+8 5n n2+9 2nlog(n) n2+2n 4n2 4n2 4n3+ 3n2 6n2+9 6n6+ n4 5n2+2n 2n+4n 3log(n)+8 5n+7 2nlog(n) 4n2 6n2+9 5n2+2n 4n3+ 3n2 2n+4n (a) O(n2) (b)  (n2) (c)  (n2)，只有中間交集部份

15 1.2 Big-O (con.t) 範例 循序搜尋(Sequential search) 二元搜尋(Binary search)
費氏數列(Fibonacci number)

16 1.2 Big-O (con.t) 循序搜尋(三種情形) Big-O為O(n)
最好的情形：搜尋的資料在第一筆，因此只要1次便可搜尋到 平均情形： (k*(1/n)) = (1/n) * k = (1/n)(1+2+…+n) = 1/n*(n(n+1)/2)= (n+1)/2 Big-O為O(n)

17 1.2 Big-O (con.t) 二元搜尋 Big-O為O(log2n+1) 因此可知二元搜尋法比循序搜尋法好
二元搜尋法乃是資料已經排序好，因此由中間的資料（mid）開始比較，便可知道欲搜尋的鍵值（key）是落在mid的左邊還是右邊，知道之後再將其中間的資料拿出來與鍵值相比，而每次所要調整的只是每個段落的起始位址或是最終位址 Big-O為O(log2n+1) 因此可知二元搜尋法比循序搜尋法好

18 1.2 Big-O (con.t) 費氏數列定義 因此 f0 = 0 f1 = 1 fn = fn-1 + fn-2 for n  2
f3 = f2 + f1 = = f4 = f3 + f2 = = 3 f5 = f4 + f3 = = 5 . fn = fn-1 + fn-2 Big-O為O(n)