版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、1,第 1 章演算法分析,,2,目次,1.1 演算法1.2 Big-O1.3 動動腦時間1.4 練習(xí)題解答,3,1.1 演算法,演算法(Algorithms)?是一解決問題(problems)的有限步驟程序產(chǎn)生解答中一步一步的程序程式效率分析方式(performance analysis)時間複雜度分析(time complexity analysis)空間複雜度分析(space complexity ana
2、lysis),4,1.1 演算法(con.t),時間複雜度分析步驟求出程式中每一敘述的執(zhí)行次數(shù)( ‘{‘ 和 ’}’ 不計算)再將這些執(zhí)行次數(shù)加總求出程式之Big-O,即為該程式之時間複雜度Ex:四個範(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í)行時間的計算∑ (每一敘述的執(zhí)行次數(shù) * 執(zhí)行該敘述所需的時間)再以Big-O來表示此程式的時間複雜度通常只考慮執(zhí)行的次數(shù)Big-O定義f(n
8、)=O(g(n)),若且唯若存在一正整數(shù)c及n0,使得f(n)≦cg(n),對所有的n,n≧n0此時,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只要取其多項式最高次方的項目即可,11,1.2 Big-O (con.t),常見的Big-O類型O(1) 稱為常數(shù)時間 (constant) ← 效率最好,執(zhí)行時間最少O(log n) 稱為對數(shù)時間 (logarithmic)O(n) 稱為線性時間 (linear)O(n log n) 稱為對數(shù)線性時間 (log linear)O(n2) 稱為平方時間 (quadratic)O(n3) 稱
10、為立方時間 (cubic)O(2n) 稱為指數(shù)時間 (exponential)O(n!) 稱為階層時間 (factorial)O(nn) 稱為n的n次方時間 ← 效率最差,執(zhí)行時間最長,12,1.2 Big-O (con.t),? 的定義 f(n) = ?(g(n)),若且唯若,存在正整數(shù)c和n0,使得f(n)≧cg(n),對所有的 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),對所有的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)費氏數(shù)列(Fibonacci number),16,1.2 Big-O (con.t),循序搜尋(三種情形)最壞的情形:搜尋的資料在檔案的最後一個,因此 需要n次才會搜尋到最好的情形:搜尋的資料在第一筆,因此只要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)開始比較,便可知道欲搜尋的鍵值(key)是落在mid的左邊還是右邊,知道之後再將其中間的資料拿出來與鍵值相比,而每次所要調(diào)整的只是每個段落的起始位址或是最終位址Big-O為O(log2n+1)因此可知
15、二元搜尋法比循序搜尋法好,18,1.2 Big-O (con.t),費氏數(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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
評論
0/150
提交評論