演算法時間複雜度 (The Complexity of Algorithms)

Presentation on theme: "演算法時間複雜度 (The Complexity of Algorithms)"— Presentation transcript:

1 演算法時間複雜度 (The Complexity of Algorithms)

2 演算法效率分析 影響程式執行時間的因素，最簡單的有 演算法(algorithm)是一解決問題的有限步驟 之程序。
機器的速度 演算法的好壞 演算法(algorithm)是一解決問題的有限步驟 之程序。 演算法的好壞，必須做複雜度的分析 (complexity analysis)。 分析演算法的複雜度，必須先求出程式中每 一敘述的執行次數，並加總起來，然後求出 其Big-O。

3 程式執行時間 例如： 執行時間 = 執行次數 * 每次執行所需的時間。
由於每一敘述所需的時間必須考慮到機器 和編譯器的功能，因此通常只考慮執行的 次數而已。 例如： x=x+1; for (i=1; i <= n; i++) for(i=1; i<=n; i++) x=x+1; for(j=1; j<=n; j++) x=x+1; 1次 n次 n2次

4 陣列 int sum(int arr[ ], int n) { int i, total=0;
for (i=0; i < n; i++) total += arr[i]; return total; } 執行次數 1 n+1 n ________ 2n+3

5 矩陣相加 假設兩矩陣a, b皆為n*n。 執行次數
void add(int a[ ][ ], int b[ ][ ], int c[ ][ ], int n) { int i, j; for(i=0; i<n; i++) for (j=0; j<n; j++) c[i][j] =a[i][j]+b[i][j]; } 執行次數 1 n+1 n(n+1) n2 ________ 2n2+2n+2

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

7 Big-O 算完程式敘述的執行次數後，通常 利用Big-O來表示此演算法的執行時 間，表示如O(n)，亦稱為該程式的 「時間複雜度(time complexity)」。 Big-O取執行次數中最高次方或最大 指數部份的項目即可。 如： 陣列元素相加為2n+3 = O(n) 矩陣相加為2n2+2n+1 = O(n2) 矩陣相乘為2n3+4n2+2n+2 = O(n3) 運用時間複雜度的觀念，我們可以 判斷該程式的執行效率是否良好。 衡量程式效率的方法還有與。

8 複雜度等級 O(1)：常數時間(constant time) O(log n)：次線性時間(sub-linear)
O(n)：線性時間(linear) O(n log n) O(n2)：平方時間(quadratic) O(n3)：立方時間(cubic) O(2n)：指數時間(exponential) O(n!)：階乘時間(factorial) 如果n很大時 → 1< log n < n < n log n < n2 < n3 < 2n < n!

9 複雜度之效率

10 Example 若ㄧ個程式執行時間是1000n^2+nlogn,求其big-O

11 複雜度分析 以循序搜尋為例： int search (int data[ ], int target, int n) { int i;
for (i=0; i < n; i++) if ( target == data[i]) return[i]; } 最佳次數：當資料在第一筆時，第一次就找 到。 最差次數：當資料不存在或資料在最後一筆時，需要N次。 平均次數： O(n) 通常比較最差次數。

12 二元搜尋— O(?) binsrch(int A[], int n, int x, int j) { lower = 1;
upper = n; while (lower <= upper) mid = (lower + upper) / 2; if (x > A[mid]) lower = mid + 1; else if (x < A[mid]) upper = mid – 1; else { j = mid; return; }

13 二元搜尋— O(?) Answer ==> O(log n)