第3章堆疊與佇列-testpageforapache

1、1,第 1 章演算法分析,,2,目次,1.1 演算法1.2 Big-O1.3 動(dòng)動(dòng)腦時(shí)間1.4 練習(xí)題解答,3,1.1 演算法,演算法(Algorithms)？是一解決問(wèn)題(problems)的有限步驟程序產(chǎn)生解答中一步一步的程序程式效率分析方式(performance analysis)時(shí)間複雜度分析(time complexity analysis)空間複雜度分析(space complexity ana

2、lysis),4,1.1 演算法(con.t),時(shí)間複雜度分析步驟求出程式中每一敘述的執(zhí)行次數(shù)( ‘{‘ 和 ’}’ 不計(jì)算)再將這些執(zhí)行次數(shù)加總求出程式之Big-O，即為該程式之時(shí)間複雜度Ex：四個(gè)範(fàn)例,5,1.1.1 陣列元素相加,執(zhí) 行 次 數(shù)int sum(int arr[], int n){int i, total=0; 1 for (i=0; i<n; i++)

3、 n+1 total+=arr[i]; nreturn total; 1} 2n+2,,,6,1.1.2 矩陣相加,執(zhí) 行 次 數(shù)void add (int a[][], int b[][], int c[][], int m, int n){for (int i=0; i < n; i++)

4、 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 矩陣相乘,執(zhí) 行 次 數(shù)void mul(int a[][], int b[][], int c[][], int n){ int i, j, k,

5、 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 + a[i][k]

6、* b[k][j]; n3 c[i][j] = sum; n2 }} 2n3+4n2+2n+2,,,8,1.1.4 循序搜尋,執(zhí) 行 次 數(shù)int search(int data[],int target, int n){　 int i; 　1 for (i = 0; i < n; i

7、++) n+1 if (target == data[i]) n return i; 1} 2n+3,,,9,1.2 Big-O,程式或演算法執(zhí)行時(shí)間的計(jì)算∑ (每一敘述的執(zhí)行次數(shù) * 執(zhí)行該敘述所需的時(shí)間)再以Big-O來(lái)表示此程式的時(shí)間複雜度通常只考慮執(zhí)行的次數(shù)Big-O定義f(n

8、)=O(g(n))，若且唯若存在一正整數(shù)c及n0，使得f(n)≦cg(n)，對(duì)所有的n，n≧n0此時(shí)，f(n)的Big-O為g(n),10,1.2 Big-O (con.t),Big-O範(fàn)例3n+2=O(n)∵當(dāng)c=4，n0=2，3n+2 ≦4n∴ 3n+2 的 Big-O 為 nl0n2+5n+1=O(n2)∵當(dāng)c=11，n0=6，10n2+5n+1 ≦11n2 ∴ l0n2+5n+1 的 Big-O 為 n2

9、由上述範(fàn)例可知，Big-O只要取其多項(xiàng)式最高次方的項(xiàng)目即可,11,1.2 Big-O (con.t),常見(jiàn)的Big-O類(lèi)型O(1) 稱(chēng)為常數(shù)時(shí)間 (constant) ← 效率最好，執(zhí)行時(shí)間最少O(log n) 稱(chēng)為對(duì)數(shù)時(shí)間 (logarithmic)O(n) 稱(chēng)為線(xiàn)性時(shí)間 (linear)O(n log n) 稱(chēng)為對(duì)數(shù)線(xiàn)性時(shí)間 (log linear)O(n2) 稱(chēng)為平方時(shí)間 (quadratic)O(n3) 稱(chēng)

10、為立方時(shí)間 (cubic)O(2n) 稱(chēng)為指數(shù)時(shí)間 (exponential)O(n!) 稱(chēng)為階層時(shí)間 （factorial）O(nn) 稱(chēng)為n的n次方時(shí)間 ← 效率最差，執(zhí)行時(shí)間最長(zhǎng),12,1.2 Big-O (con.t),? 的定義 f(n) = ?(g(n)),若且唯若，存在正整數(shù)c和n0，使得f(n)≧cg(n)，對(duì)所有的 n，n≧n0 範(fàn)例3n+2=?(n)∵當(dāng)c=3，n0=1，3n+2≧3n∴ 3

11、n+2 的 ? 為 n,13,1.2 Big-O (con.t),? 的定義 f(n)= ? (g(n)),若且唯若，存在正整數(shù)c1，c2及n，使得c1*g(n)≦f(n)≦c2*g(n)，對(duì)所有的n，n≧n0範(fàn)例3n+1= ?(n)∵當(dāng) c1=3，c2=4，且n0=2，3n≦ 3n+1 ≦4n ∴ 3n+1 的 ? 為 n,14,1.2 Big-O (con.t),Big-O, ?, ? 的表示情形,,,,,3

12、log(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+

13、2n,15,1.2 Big-O (con.t),範(fàn)例循序搜尋(Sequential search)二元搜尋(Binary search)費(fèi)氏數(shù)列(Fibonacci number),16,1.2 Big-O (con.t),循序搜尋(三種情形)最壞的情形：搜尋的資料在檔案的最後一個(gè)，因此 需要n次才會(huì)搜尋到最好的情形：搜尋的資料在第一筆，因此只要1次便可搜尋到平均情形： (k*(1/n)) = (1/n) *

14、 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),二元搜尋二元搜尋法乃是資料已經(jīng)排序好，因此由中間的資料（mid）開(kāi)始比較，便可知道欲搜尋的鍵值（key）是落在mid的左邊還是右邊，知道之後再將其中間的資料拿出來(lái)與鍵值相比，而每次所要調(diào)整的只是每個(gè)段落的起始位址或是最終位址Big-O為O(log2n+1)因此可知

15、二元搜尋法比循序搜尋法好,18,1.2 Big-O (con.t),費(fèi)氏數(shù)列定義 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