演算法分析(Algorithm

1、12資料與資訊 資料 ( data ) 的定義：用具體符號表示，而能夠被計算機處理的資訊 (information)資料強調符號本身，而資訊則強調資料所呈現出來，經過人們分析、理解並領會的事實我們將在資料結構這門課中探討計算機系統所儲存以及處理的資料，並且學習如何組織這些資料，以及處理這些資料的方法3n演算法（Algorithms）是一解決問題（problems）的有限步驟程序。n簡單的問題：n連加100個數字，其演算法為。n讀入50字元，其演算法為。n將20個學生的名字加以排序，其演算法為。 4n較複雜的問題:n判斷數字x是否在一已排序好的數字串列s中n其演算法為：1.從s串列的第一個元素開

2、始，2.依序的比較，直到x被發現或s串列已達盡頭。假使x被找到，則印出Yes；否則，印出No。5n當問題很複雜時，上述敘述性的演算法就難以表達出來。因此，演算法大都以類似的程式語言表達之 - pseudo code (English like)n繼而利用所熟悉的程式語言執行之nC, C+, Java6演算法與資料結構 演算法演算法 (algorithm) 的定義：“在有限步驟內解決數學問題的程序”。在計算機科學的領域中，演算法泛指“適合被實作為計算機程式的解題方法” 演算法通常具有以下五個特性：一 輸入 (Input)二 明確性 (Definiteness)三 正確性 (Correctness

3、)或稱有效性(Effectiveness)四 有限性 (Finiteness)五 輸出 (Output)7例1: 歐幾里得演算法 計算兩個自然數的最大公因數 (Greatest Common Divisor, GCD) 演算法描述如下：步驟 1. 輸入兩個自然數 A , B步驟 2. A 除以B，餘數為 R步驟 3. 如果 R 為零，則跳至步驟 5步驟 4. AB，BR，跳至步驟 2步驟 5. B 即為 GCD8這些敘述符合演算法的特性：一 輸入 (Input) ：兩個自然數A, B 二 明確性 (Definiteness) ：以逐步追蹤法 一步一步執行敘述，不造成混淆 三 正確性 (Corr

4、ectness) ：以兩組A,B代入執行均得到正確結果四 有限性 (Finiteness) ：A,B,R在第二圈以後都會愈來愈小（因為每一圈 R 一定小於 B）。由於他們都是正整數，所以R終會等於零 五 輸出 (Output) ：A,B 的最大公因數 9R = A MOD BA BB R開 始是輸入自然數A,BR = 0 ?B為GCD結 束否 用流程圖來描述這個演算法： 10n一個客觀的方法來比較程式的優劣n“他的程式寫得比我好嗎？”n一個客觀的方法來評量程式的效率-複雜度分析 (complexity analysis)n執行的時間 (execution time)n儲存的空間 (storag

5、e space)-不考慮11在程式或演算法中，每一敘述（statement)的執行時間為：(1)此敘述執行的次數(2)每一次執行所需的時間兩者相乘即為此敘述的執行時間。12n由於每一敘述所須的時間必需實際考慮到機器和編譯器的功能，因此通常只考慮執行的次數而已。13計算 n 階層 ( n! ) 的函式如下： int factor( int n) 0 int result, i ;1 result = 1 ;2 i = 1 ;3 while ( i 0 時n 0，執行次數為 3n+4次，如果 n= 0，執行次數為 4次15A. 單層迴圈1 for ( i = 1 ; i n ; i+) 2 res

6、ult = result + 1 ;計算每一行敘述被執行的次數：行號 1: 條件成立 (如果 in)，執行次數為 n-1次，條件不成立 (如果 i=n)，執行次數為 1次； 總執行的次數為 n次。行號 2: 迴圈計數器i的範圍是1n-1，因此迴圈共重複 n-1 次，總執行的次數為 n-1次。簡單的數學模式： n-1總次數 = 1 = n-1 i=116B. 雙層迴圈、內圈固定次數 1 for ( i = 1 ; i = n ; i+)2for ( j = 1 ; j n ; j+) 3 result = result + 1 ; 計算每一行敘述被執行的次數：行號 1: 條件成立執行次數為n次，

7、條件不成立執行次數為 1 次； 總執行的次數為n+1次。行號 2: 迴圈計數器j範圍是1n-1，條件成立共執行n*(n-1)次， 迴圈條件不成立共n次，總執行的次數為 n*(n-1)+n次。行號 3: 外圈迴圈計數器i的範圍是1n，內圈迴圈計數器j的範圍 是1n-1，外圈每執行1圈，內圈就會執行n-1圈。而外 圈會執行n圈，因此，第3行敘述共將執行 n*(n-1)次。17C. 雙層迴圈、內圈不固定次數 1 for ( i = 1 ; i = n ; i+)2for ( j = i+1 ; i = n ; j+) 3 result = result + 1 ; 計算每一行敘述被執行的次數：行號

8、1: 條件成立執行次數為n次，條件不成立執行次數為1次； 總執行的次數為 n+1 次。行號 2: 迴圈計數器 j 的範圍是 i + 1, , n，( i = 1, 2, ., n; j = 2, 3, 4, ., n)，因此，迴圈條件成立共執行 (n-1) +(n-2)+ . +3+2+1+0 = n*(n-1)/2 次，迴圈條件 不成立共 n次，總執行的次數為 n*(n-1)/2 + n 次。行號 3: 第 3 行敘述的次數執行為 n * (n-1) / 2 次。18數學模式：數學模式： n n-1 n n 總次數總次數 1 = ( n-1-(i+1)+1) = (n i)= n2-n*(n

9、+1)/2 = n*(n-1)/2 i=1 j=i+1 i=1 i=1 i 的值j 的範圍第3行執行次數12 nn-123 nn-234 nn-3 n-1n n1nn+1 n0 總次數 n * ( n-1 ) / 2 19n在分析演算法時，一般稱敘述的執行次數為order of magnitude。n而整個演算法的order of magnitude為演算法中每一敘述的執行次數之和。n算完程式敘述的執行次數後，通常利用Big-O來表示此演算法執行的時間。n所以下列的(a) 、(b) 、(c)中，x=x+1的order of magnitude分別為1，n，n220:x = x + 1;:(a)

10、1for (i = 1; i= n; i+) x = x + 1;:(b)nfor (i = 1; i= n; i+) for (j = 1; j0, n n0 , f (n) c*g(n)用口語解釋為：f(n) 取Big-O符號為O( g(n)，當 n 夠大的時候，g(n)相當於是f(n)的上限。22n請看下列範例：n(a) 3n+2=O(n) 我們可找到c=4，n0=2,使得3n+2 4nn(b) 10n2+5n+1=O(n2) 我們可以找到c=11, n0=6使得10n2+5n+1 11n2 n(c) 7*2n +n2+n=O(2n) 我們可以找到c=8, n0=5使得7*2n +n2

11、+n 8*2n23c * g(n)f(n)n24nO(1) 稱為常數時間(constant)nO(log n) 稱為次線性時間(sub-linear)nO(n) 稱為線性時間(linear)nO(n log n) 稱為n log nnO(n2) 稱為平方時間(quadratic)nO(n3) 稱為立方時間(cubic)nO(2n) 稱為指數時間(exponential)nO(n!) 稱為階層時間nO(nn) 稱為n的n次方時間252nn3n2nlog nnO(1) O(log n) O(n) O(n log n) O (n2) O (n3) O (2n) O (n!) O (nn)26log

12、n nn2 n3 2n 0 11 1 2 1 24 8 4 2 416 64 16 3 864 512 256 4 16256 4096 65536 5 321024 32768 2147483648當當 n 愈大則其間的差異也愈大愈大則其間的差異也愈大27f(n) = (g(n) ，若且唯若存在一正整數 c 及 n0 ，使得 f(n) c*g(n)，對所有的n，n n0。用口語解釋為：f(n) 取符號為( g(n)，當 n 夠大的時候， g(n)相當於是f(n)的下限。nExamplesn3n+2 = (n) as 3n+2 3n for all n 1.n10n2+4n+2 = (n2) as 10n2+4n+2 n2 for n 1.28f(n) = (g(n) ，若且唯若，存在正整數c1, c2 及 n0，