1、1,第 1 章演算法分析,2,目次,1.1 演算法1.2 Big-O1.3 動動腦時間1.4 練習題解答,3,1.1 演算法,演算法(Algorithms)？是一解決問題(problems)的有限步驟程序產生解答中一步一步的程序程式效率分析方式(performance analysis)時間複雜度分析(time complexity analysis)空間複雜度分析(space complexity analysis),4,1.1 演算法(con.t),時間複雜度分析步驟求出程式中每一敘述的執行次數( 和 不計算)再將這些執行次數加總求出程式之Big-O，即為該程式之時間複雜度Ex：四個範例,
2、5,1.1.1 陣列元素相加,執 行 次 數int sum(int arr, int n)int i, total=0; 1 for (i=0; in; i+) n+1 total+=arri; nreturn total; 1 2n+2,6,1.1.2 矩陣相加,執 行 次 數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) cij = aij + bij n2 2n2+2n+1,7,1.1.3 矩陣相乘,執 行 次 數void mul(in
3、t a, int b, int c, int n) int i, j, k, sum; 1 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 + aik * bkj; n3 cij = sum; n2 2n3+4n2+2n+2,8,1.1.4 循序搜尋,執 行 次 數int search(int data,int target, int n) int i; 1 for (i = 0; i n; i+) n+1 if (target =
4、 datai) n return i; 1 2n+3,9,1.2 Big-O,程式或演算法執行時間的計算 (每一敘述的執行次數 * 執行該敘述所需的時間)再以Big-O來表示此程式的時間複雜度通常只考慮執行的次數Big-O定義f(n)=O(g(n)，若且唯若存在一正整數c及n0，使得f(n)cg(n)，對所有的n，nn0此時，f(n)的Big-O為g(n),10,1.2 Big-O (con.t),Big-O範例3n+2=O(n)當c=4，n0=2，3n+2 4n 3n+2 的 Big-O 為 nl0n2+5n+1=O(n2)當c=11，n0=6，10n2+5n+1 11n2 l0n2+5n+
5、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次方時間
6、效率最差，執行時間最長,12,1.2 Big-O (con.t), 的定義 f(n) = (g(n),若且唯若，存在正整數c和n0，使得f(n)cg(n)，對所有的 n，nn0 範例3n+2=(n)當c=3，n0=1，3n+23n 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，nn0範例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, , 的表示情形,
7、3log(n)+85n+7 6n2+92nlog(n) 5n2+2n4n2,4n24n3+ 3n2 6n2+96n6+ n4 5n2+2n2n+4n,(a) O(n2) (b) (n2) (c) (n2)，只有中間交集部份,3log(n)+85n+7 2nlog(n),4n3+ 3n22n+4n,4n26n2+95n2+2n,15,1.2 Big-O (con.t),範例循序搜尋(Sequential search)二元搜尋(Binary search)費氏數列(Fibonacci number),16,1.2 Big-O (con.t),循序搜尋(三種情形)最壞的情形：搜尋的資料在檔案的最後
8、一個，因此 需要n次才會搜尋到最好的情形：搜尋的資料在第一筆，因此只要1次便可搜尋到平均情形： (k*(1/n) = (1/n) * k = (1/n)(1+2+n) = 1/n*(n(n+1)/2)= (n+1)/2Big-O為O(n),17,1.2 Big-O (con.t),二元搜尋二元搜尋法乃是資料已經排序好，因此由中間的資料（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因此 f2 = f1 + f0 = 1 f3 = f2 + f1 = 1 + 1 = 2 f4 = f3 + f2 = 2 + 1 = 3 f5 = f4 + f3 = 3 + 2 = 5 . . fn = fn-1 + fn-2Big-O為O(n),
