1、算法設計與分析Design and Analysis to Algorithms1教材： 算法設計與分析 呂國英主編 清華大學出版社 計算機算法基礎 余祥宣等編 華中科大出版社參考書： 算法設計與分析 王曉東編 清華大學出版社 計算機算法導引設計與分析 盧開澄編 清華大學出版社 學時：4學時/周2與數據結構的區別：考慮問題的角度：數據結構關心不同的數據結構在解題中的作用和效率；算法關心不同設計技術的適用性和效率。考慮問題的高度：數據結構關心的是解具體問題，算法不僅如此，它提供一種解決問題的通用方法。與其他課程的關系高級程序設計語言（C, C+） 數據結構 算法設計與分析 3 廣播操圖解是廣播操

2、的算法;菜譜是做菜的算法；歌譜是一首歌曲的算法；空調說明書是空調使用的算法等What？4例1：給出求1+2+3+4+5的一個算法。算法1 按照逐一相加的程序進行。第一步 計算1+2,得到3；第二步 將第一步中的運算結果3與3相加,得到6；第三步 將第二步中的運算結果6與4相加,得到10；第四步 將第三步中的運算結果10與5相加,得到15。5算法2 可以運用公式直接計算;第一步 取n=5;第二步 計算第三步 輸出運算結果。6例2：三個牧師和三個野人過河，只有一條能裝下兩人的船，在河的任一邊或者船上，若野人人數大于牧師人數，那么牧師就會有被吃掉的危險。你能不能找出一種安全的渡河算法呢？第一步 兩個

3、野人先過河，一個野人回來； 第二步 再兩個野人過河，一個野人回來； 第三步 兩個牧師過河，一個野人和一個牧師回來； 第四步 兩個牧師過河，一個野人回來； 第五步 兩個野人過河，一個野人回來； 第六步 兩個野人過河。 7算法廣義：在解決問題時，按照某種機械步驟一定可以得到問題結果（有解時給出問題的解，無解時給出無解的結論）的處理過程。狹義：用計算機解決問題的方法和步驟的描述。820 世紀最偉大的科學技術發明-計算機；計算機是對人腦的模擬，它強化了人的思維；沒有軟件的支持，超級計算機只是一堆廢鐵而已。軟件的核心就是算法 ！Why to study？程序數據結構算法9現代科學研究的三大支柱理論研究科

4、學實驗科學計算研究算法1021世紀信息社會的兩個主要特征：“計算機無處不在”“數學無處不在”21世紀信息社會對科技人才的要求：-會“用數學”解決實際問題。-會用計算機進行科學計算。11本課程為計算機科學與技術學科本科生的專業課。 How to study？通過該課程的學習，對計算機常用算法有一個全 盤的了解，掌握通用算法的一般設計方法。學會對算法的時間和空間復雜性進行分析，掌握提高算法效率的方法和途徑。(評價有效算法)12 一般計算機對現實問題無能為力，需要人類對問題抽象化、形式化后才能去機械的執行。學習目標：“用計算機求解問題”問題分析：準確、完整地理解和描述問題 數學模型建立算法設計與選擇

5、：創造性的活動算法表示：思想的表示形式算法分析：算法時空特性分析算法實現程序調試：測試結果整理文檔編制13算法概述141. 什么是算法？ 算法是解一確定類問題的任意一種特殊的方法。 在計算機科學中，算法是使用計算機解一類問題的精確、有效方法的代名詞： 算法是一組有窮的規則，它規定了解決某一特定類型問題的一系列運算。1.1 算法 152. 算法的五個重要特性 確定性、能行性、輸入、輸出、有窮性/有限性1）確定性 算法每種運算必須有確切定義，不能有二義性。 例：不符合確定性的運算： 5/0 將6或7與x相加 未賦值變量參與運算163）輸入 每個算法有0個或多個輸入。這些輸入是在算法開始之前給出的量

6、，取自于特定的對象集合定義域4）輸出 一個算法產生一個或多個輸出，這些輸出是同輸入有某種特定關系的量。5）有窮性/有限性 一個算法總是在執行了有窮步的運算之后終止。2）能行性 算法中有待實現的運算都是基本的運算，原理上每種運算都能由人用紙和筆在有限的時間內完成。 例：整數的算術運算是“能行”的 實數的算術運算是“不能行”的17 計算過程：只滿足確定性、能行性、輸入、輸出四個特性但不一定能終止的一組規則。 準確理解算法和計算過程的區別： 不能終止的計算過程：操作系統 算法是“可以終止的計算過程”。 算法的時效性：只能把在相當有窮步內終止的算法投 入到計算機上運行。18一般求d=gcd(m,n)的

7、過程用自然語言可以描述如下： (1) 找出m的素因子。 (2) 找出n的素因子。 (3) 從第(1) (2)步求得的素因子中找出m，n的公共素因子。 (4) 將第(3)步找到的素因子相乘，其結果即為m，n的最 大公約數。求兩個正整數的最大公約數。例1.1 數學模型：m，n0 整數，求d，d能整除m，n，且m/d與n/d互質。19計算gcd(m,n)的短除法算法設計：計算機沒有“宏觀”能力來“看出”公約數，但通過“枚舉嘗試”（逐個嘗試）就可以“試出”m,n有哪些是公約數，并將這些公約數“累乘”，就能得到最大公約數。算法描述如下：main( )int m,n,d,i; input (m,n); d

8、=1； /變量d是為累乘因數而設置的； for (i=2; i=m and i=n; i+) /“枚舉”可能的公約數 while (m mod i=0 and n mod i=0 ) /“試”i是否為公約數 d=d*i; m=m/i; n=n/i; print(d ,“is maximal common divisor”);為什么用while?20計算gcd(m,n)的連續整數檢測算法第一步：將minm,n的值賦給d。第二步：m除以d，若余數為0，進入第三步；否則第四步。第三步：n除以d，若余數為0，返回d值(結果)；否則第四步。第四步：把d的值減1，返回第二步。 例如：對于60和24這兩個數

9、，該算法會先嘗試24，然后是 23，這樣一直嘗試到12，算法結束。同一個問題有不同的解決方法！ 21歐幾里德算法gcd ( m, n ) = gcd ( n, m mod n )gcd ( 24, 18 ) = gcd ( 18, 6 ) = gcd ( 6, 0 ) = 6 輸入 正整數m和n 輸出 m和n的最大公因子如果n = 0, 計算停止返回m, m即為結果；否則繼續2。記r為m除以n的余數，即r=m mod n。把n賦值給m，把r賦值給n，繼續1。偽代碼如下： Euclid(m, n) while n 0 r = m n; m = n; n = r; Beginn=0?r=m mod

10、 nm=nn=rendNY同一個算法有不同的表達方式！22 下面是初學者易發生的問題，提前指出以引起注意： 通過輸入語句增加算法的通用性。 會忘掉“輸出”或在模塊間傳遞處理的數據結果。 易忽略細節造成“死循環”。 出現語序方面的錯誤，特別是雙重循環中指令常有嵌 套錯誤。 注意學習和總結。 用大腦“運行”算法是學習算法很好的方法。 解題時要學會擇優。簡單說擇優要考慮四個方面： 可讀性、可修改性、時間效率和空間效率。233.從算法到實現-算法基本技巧舉例a. 算術運算的妙用例1.2 開燈問題b. 巧用“標志量”例1.3 判定輸入n個數據互不相等例1.4 冒泡排序c. 信息數字化例1.5 警察抓小偷

11、d. 學會找規律例1.6 數組移位24a. 算術運算的妙用-例1.2開燈問題算術運算：加減乘除。例1.2 開燈問題從前，有從1到n依次編號的n個同學和n 盞燈。1號同學將所有的燈都關掉；2號同學將編號為2的倍數的燈都打開；3號同學則將編號為3的倍數的燈作相反處理（該號燈如打開的，則關掉；如關閉的，則打開）；以后的同學都將自己編號的倍數的燈，作相反處理。問：經n個同學操作后，哪些燈是打開的？25問題分析：1）用數組表示某種狀態，這里定義有n個元素的a數組，它的每個下標變量ai視為一燈，i表示其編號。ai=1表示燈處于打開狀態，ai=0表示燈處于關閉狀態。此用法也稱為“乒乓開關”。簡化邏輯表達式、

12、減少條件判斷2）實現將第i 燈作相反處理的操作：條件語句if表示：if ai = 1 ai = 0；if ai = 0 ai = 1； 通過算術運算更簡練、逼真： ai=1-ai。a. 算術運算的妙用-例1.2問題分析/建模26a. 算術運算的妙用-例1.2-算法設計int a1000;輸入n的數值；關閉所有燈，即a1an置為0；第2個學生-第n個學生(學生i)進行操作：操作對象：數組a，燈編號含因數i，即ai*k ；操作： ai*k = 1 - ai*k ；輸出燈的開關狀態。27建立一個充分大的數組int a1000;輸入n的數值；關閉所有燈，即a1an置為0；第2-第n個學生(每個學生i)

13、進行操作：操作對象：數組a，燈編號含因數i，即ai*k操作：ai*k = 1 - ai*k ；輸出燈的開關狀態。void main( ) int n,a1000,i,k; scanf(%d,&n); for( i=1;i=n;i+) ai=0; for( i=2;i=n;i+) k=1; while ( i*k = n) ai*k = 1 - ai*k; k = k + 1; for( i=1;i第n-1個(每個元素i)操作與第i+1第n元素(每個元素j)比較，若相等則標志量置0，循環中斷；若flag=1，則無重復；反之，有重復。b 巧用“標志量”-例1.3-算法設計30b 巧用“標志量”-例

14、1.3 實現void main() int a100,i,j,flag,n; scanf(%d,&n); for (i=1;i=n;i=i+1) scanf(%d,&ai); flag = 1; for (i=1;i=n-1;i=i+1) for (j=i+1;j=n;j=j+1) if(ai=aj) flag = 0; break; if (flag = 1) printf(No repeatn); else printf(Repeatn);31例1.4冒泡排序 排序過程 1、比較第一個記錄與第二個 記錄，若關鍵字為逆序則交換；然 后比較第二個記錄與第三個記錄； 依次類推，直至第 n -1

15、個記錄和第 n 個記錄比較為止第一趟冒泡 排序，結果關鍵字最大的記錄被安 置在最后一個記錄上。 2、對前 n-1 個記錄進行第二 趟冒泡排序，結果使關鍵字次大的 記錄被安置在第 n-1 個記錄位置。 3、重復上述過程，直到 “在 一趟排序過程中沒有進行過交換記 錄的操作” 為止。 初 始 關 鍵 字 49 38 65 97 76 13 27 49 第 一 趟 排 序 49 38 49 97 76 97 97 13 97 97 27 97 97 49 97 38 49 65 76 13 27 49 9738 49 65 13 27 49 76 第 二 趟 排 序 38 49 13 27 49 6

16、5 第 三 趟 排 序 38 13 27 49 49 第 四 趟 排 序 13 27 3849 第 五 趟 排 序 13 27 38 第 六 趟 排 序 for ( j = 1; j n ; j + +) if ( r j +1 r j ) r j r j + 1 ; for ( j = 1; j n -1; j + +) if ( r j +1 1; i - - ) i ; while ( i 1) / while i = n ; i = k ; Void BubbleSort(SqList &L) 冒泡排序算法 初 始 關 鍵 字 49 38 65 97 76 13 27 49 k = j

17、 ; /交換的位置 k = 1 ; 32c 信息數字化-例1.5 警察抓小偷一些表面上看是非數值的問題，但經過進行數字化后，就可方便進行算法設計。例1.5 警察抓小偷警察局抓了a，b，c，d四名偷竊嫌疑犯，其中只有一人是小偷。審問中 a說：“我不是小偷。” b說：“c是小偷。” c說：“小偷肯定是d。” d說：“c在冤枉人。”現在已經知道四個人中三人說的是真話，一人說的是假話，問到底誰是小偷？33c 信息數字化-例1.5 -問題分析問題分析：可通過循環，每次假設一名嫌疑犯為小偷，代入問題系統，檢驗是否只有一句假話。這種讓所有可能解都進行檢驗，以求得真解的方法稱為“枚舉嘗試法”，也是“蠻力法”、

18、“暴力法” 。為方便設計程序，將a,b,c,d將四個人進行編號，號碼分別為1，2，3，4。34c 信息數字化-例1.5 -算法設計算法設計：用變量x存放小偷的編號，則x的取值范圍從1取到4，就假設了他們中的某人是小偷的所有情況。四個人所說的話就可以分別寫成：a說的話：x1b說的話：x=3c說的話：x=4d說的話：x4或not(x=4)注意:在x的枚舉過程中，當這四個邏輯式的值相加等于3時，即表示“四個人中三人說的是真話，一人說的是假話”。 if (x!=1)+(x=3)+(x=4)+(x!=4)=3)35c 信息數字化-例1.5 -實現#include stdafx.hvoid main()i

19、nt x;for(x=1;x=4;x=x+1)if (x!=1)+(x=3)+(x=4)+(x!=4)=3)printf(%c is a thief,char(64+x);36d 學會找規律-例1.6 數組移位例1.6 數組中有n個數據，要將它們順序循環向后移k位，即前面的元素向后移k位，后面的元素則循環向前移k位，例：0、1、2、3、4循環移3位后為： 2 、3、4、0、1。考慮到n會很大，不允許用2*n以上個空間來完成此題。37d 學會找規律-例1.6-問題分析(思路1)問題分析1：若題目中沒有關于存儲空間的限制，我們可以方便地開辟兩個一維數組，一個存儲原始數據，另一個存儲移動后的數據。開

20、始部分的元素從前向后移，容易確定；但數組中后k個元素是從后向前移，如何確定？38d 學會找規律-例1.6-問題分析(思路1)void alg1() int a100,b100,i,n,k; scanf(%d,%d,&n,&k); for (i=0;in;i=i+1) scanf(%d,&ai); for (i=0;in;i=i+1) b(k+i) % n = ai; for (i=0;in，這樣移動會出現重復操作,可以在輸入數據后，執行k = k mod n; 以保證不出現重復移動的問題。這個算法的移動（賦值）次數為k*n。當n較大時不是一個好的算法。void alg2() int a100,

21、i,j,n,k,temp; scanf(%d,%d,&n,&k); for (i=0;in;i=i+1) scanf(%d,&ai); for (i=0;i0;j=j-1) aj = aj-1; a0 = temp; for (i=0;in;i=i+1) printf(%d,ai); printf(n);41d學會找規律-例1.6-問題分析 (思路3)問題分析3 ：利用一個臨時存儲空間，把每一個數據一次移動到位。1）一組循環移動的情況：通過計算我們可以確定某個元素移動后的具體位置，如n=5, k=3時：0、1、2、3、4循環移3位后為2、3、4、0、1。可通過計算得出0移到3的位置，3移到1的

22、位置，1移到4的位置，4移到2的位置，2移到0的位置；一組移動（0-3-1-4-2-0）正好將全部數據按要求進行了移動。這樣只需要一個輔助變量，每個數據只需一次移動就可完成整個移動過程。如果算法就這樣按一組移動去解決問題，就錯了。因為還有其它情況。422）多組循環移動的情況：算法不能只按一組移動去解決問題。看下一個例子，當n=6，k=3時， 0、1、2、3、4、5經移動的結果是3、4、5、0、1、2. 共要進行三組循環移動（0-3，1-4，2-5）才能將全部數據操作完畢。循環移動的組數，與k、n是怎么樣的關系呢？我們再看一個例子，當N=6，K=2時， 0、1、2、3、4、5經移動的結果是4、5

23、、0、1、2、3。 0移到2的位置，2移到4的位置，4移到0的位置，一組移動完成了3個數據的移動，接下來，還有一組1-3-5-1。共進行二組循環移動，就能將全部數據移動完畢。d學會找規律-例1.6-問題分析 (思路3)43d學會找規律-例1.6-建模/算法設計 (思路3)數學模型：循環移動的組數等于N與K的最大公約數。算法設計：1）編寫函數，完成求n , k最大公約數m的功能。2）進行m組循環移動。3）每組移動，和算法2一樣，通過計算可以確定某個元素移動后的具體位置。在移動之前，用臨時變量存儲需要被覆蓋的數據。44d學會找規律-例1.6-實現 (思路3)void alg3() int a100

24、,b0,b1,i,j,n,k,m,tt; scanf(%d,&n); scanf(%d,&k); for(i=0;in;i=i+1) scanf(%d,&ai); m=gcd(n,k); for(j=0;jm;j=j+1) b0=aj; tt=j; for(i=0;in/m;i=i+1) tt=(tt+k) % n; b1=att; att= b0; b0=b1; for(i=0;in;i=i+1) printf(%d,ai); printf(n);45算法 = 控制結構 + 原操作表示算法的語言主要有：自然語言流程圖盒圖PAD圖偽代碼計算機程序設計語言1.2 算法描述 461自然語言自然語言

25、是人們日常所用的語言。自然語言描述算法的缺點： 自然語言的歧義性易導致算法執行的不確定性。 自然語言語句一般太長導致描述的算法太長。 當算法中循環和分支較多時就很難清晰表示。 不便翻譯成程序設計語言理解的語言。47 2流程圖 主要缺點： 使算法設計人員過早考慮算法控制流程，而不去考慮全局結構，不利于逐步求精。 隨意性太強，結構化不明顯。 不易表示數據結構。 層次感不明顯。NYr等于0?輸出n的值輸入正整數m和n開始結束m n; n rrm被n除的余數rm被n除的余數483盒圖（NS流程圖） （1）盒圖具有以下優點： 層次感強、嵌套明確。 支持自頂向下、逐步求精。 容易轉換成高級語言源算法。（2

26、）主要缺點： 不易擴充和修改，不易描述大型復雜算法。輸入正整數m和n rm被n除的余數 m n; n rrm被n除的余數 當r不等于 0輸出n的值 49 PAD圖的主要優點： 設計出來的算法必是結構化的。PAD圖描繪的算法結構清晰。用PAD圖表現的算法邏輯，易讀、易懂、易記。容易用軟件工具自動將PAD圖轉換成高級語言源算法。既可用于表示算法邏輯，也可用于描繪數據結構。支持自頂向下、逐步求精。缺點：由于是圖形符號書寫、編輯、錄入不方便。4 PAD圖 問題分析圖(Problem Analysis Diagram, 簡稱PAD)表示的算法是一個二維樹形結構圖，層次感強、嵌套明確且有明確的控制流程。5

27、0例：問題分析圖實例515偽代碼 偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法的工具。它不用圖形符號，因此書寫方便，格式緊湊，易于理解，便于用計算機程序設計語言實現。 如：類SPARKS/類C/類C526程序設計語言的缺點： 算法的基本邏輯流程難于遵循。與自然語言一樣，程序設計語言也是基于串行的，當算法的邏輯流程較為復雜時這個問題就變得更加嚴重。 特定程序設計語言編寫的算法限制了與他人的交流，不利于問題的解決。 要花費大量的時間去熟悉和掌握某種特定的程序設計語言。 要求描述計算步驟的細節而忽視算法的本質。 需要考慮語法細節，而擾亂算法設計的思路。 考慮到程序設計語言不斷更新，不

28、適于描述算法。 算法設計一般不用程序設計語言直接描述。531. 算法分析的目的 通過對算法分析，在把算法變成程序實際運行前，就知道為完成一項任務所設計的算法的好壞，從而運行好算法，改進差算法，避免無益的人力和物力浪費。 1.3 算法分析542. 重要的假設和約定1）計算機模型的假設 計算機形式理論模型 ：Turing機模型 通用計算機模型： 單處理器：每次執行程序中一條指令 有足夠的“內存” 能在固定的時間內存取數據單元552）計算的約定確定使用什么樣的運算及其執行時間。從計算時間上，運算的分類： 時間囿界于常數的運算：每種運算的執行時間不同，但一般只花 一個固定量時間（單位時間）就可完成。

29、基本算術運算 字符運算 賦值運算 過程調用等562）計算的約定 其他運算：特點：運算時間無定量 字符串操作：與字符串中字符的數量成正比。 記錄操作：與記錄的屬性數、屬性類型等有關。 如何分析非時間囿界于常數的運算？ 如：Tstring = Length（String）* tchar算法的執行時間=Fi*tiFi是算法中用到的某種運算i的次數， ti是該運算執行一次所用時間。571.有些計算機需要用戶提供程序運行時 間的上限，一旦達到這個上限，程序 將被強制結束。2.正在開發的程序可能需要提供一個滿 意的實時響應。時間復雜性和空間復雜性3.算法復雜性為什么要考慮時間復雜性？581.多用戶系統中運

30、行時，需指明分配給該程序的內存大小。2.可提前知道是否有足夠可用的內存來運行該程序。3.一個問題可能有若干個內存需求各不相同的解決方案，從中擇取。4.利用空間復雜性來估算一個程序所能解決問題的最大規模。考慮程序的空間復雜性的理由：594. 如何進行算法分析？事前分析：就算法本身，通過對其執行性能的理論分析， 得出關于算法特性時間和空間的一個特征 函數（、）與計算機軟硬件沒有直接 關系。事后測試：將算法編制成程序后放到計算機上運行，收集 其執行時間和空間占用等統計資料，進行分析 判斷直接與物理實現有關。601）事前分析目的：試圖得出關于算法執行特性的一種形式描 述，以“理論上”衡量算法 “好壞”

31、。如何給出反映算法執行特性的描述？ 最直接方法：統計算法中各種運算的執行情況： 運用了哪些運算 每種運算被執行的次數 該種運算執行一次所花費的時間 算法的執行時間=Fi*ti61估算執行時間的方法 選擇一種或多種（如加、乘和比較等），然后確定這種（些）操作分別執行了多少次。令n代表程序實例特征，則執行時間計算公式為：TP（n）= c1ADD(n) + c2SUB(n) + c3MUL(n) + c4DIV(n)+c1、c2、c3、c4分別表示一次加、減、乘、 除操作所需的時間。函數ADD (n) 、SUB (n) 、MUL (n) 、DIV (n)分別表示程序P中，所使用的加、減、乘、除操作的

32、次數。這種方法是否成功取決于識別關鍵操作的能力，這些關鍵操作對時間復雜性的影響最大。一條語句在整個程序運行時實際執行時間= 頻率計數 * 每執行一次該語句所需的時間62頻率計數：算法中語句或運算的執行次數。 例： x=x+y for (i =1;i=n;i+) for (i =1;i=n;i+) x=x+y; for (j =1;j=n;j+) x=x+y; (a) (b) (c) 分析： (a)： x=x+y執行了1次 (b)： x=x+y執行了n次 (c)： x=x+y執行了n2次 注：在事前分析中，只限于確定與所使用機器及其他環境因素無關的頻率計數，依此建立一種理論上分析模型。63數量級

33、語句的數量級：語句的執行頻率。例：1，n ，n2 算法的數量級：算法包含所有語句的執行頻率之和。 算法的數量級從本質上反映了一個算法的執行特性。 例：求解同一問題的三個算法分別具有n, n2 , n3數量級。 若n=10，則可能的執行時間將分別是10，100，1000 個單位時間與環境因素無關。64 計算時間/頻率計數的表示函數 通過事前分析給出算法計算時間（頻率計數）的一個函數表示形式，一般記為與輸入規模n有關的函數形式：f(n)注：最高次項與函數整體的關系空間特性分析（與時間特性的分析類似，略） 652）事后測試目的：運行程序，確定程序實際耗費的時間與空間，驗證先前的分析結論包括正確性、執

34、行性能等，比較、優化所設計的算法。分析手段：作時、空性能分布圖。665. 計算時間的漸近表示記：算法的計算時間為f(n) 數量級限界函數為g(n)其中， n是輸入或輸出規模的某種測度。 f(n)表示算法的“實際”執行時間與機器及語言有關。 g(n)是形式簡單的函數，如nm，logn，2n，n!等。是事前分析中通過對計算時間或頻率計數統計分析所得的與機器及語言無關的函數。 以下給出算法執行時間：上界（）、下界（）、“平均”（ ）的定義。67漸進意義下的記號：O,定義1.1 如果存在兩個正常數c和N0,對于所有的NN0，有|f(N)|C|g(N)|，則記作：f(N)= O(g(N)。N0f(N)g

35、(N)當說一個算法具有O(g(n)的計算時間時，指的就是如果此算法用n值不變的同一類數據在某臺機器上運行時，所用的時間總是小于g(n)的一個常數倍。g(n)是計算時間f(n)的一個上界函數，f(n)的數量級就是g(n)。68Example因為對所有的N1有3N4N，所以有3N=O(N);因為當N1時有N+10241025N，所以有N+1024=O(N);因為當N10時有2N2+11N-103N2,所以有 2N2+11N-10=O(N2)因為對所有N1有N2N3,我們有N2=O(N3)作為一個反例N3O(N2),因為若不然，則存在正的常數C和自然數N0,使得當NN0，有N3CN2,即NC。顯然，

36、當取N=maxN0,C+1時這個不等式不成立，所以N3O(N2)69多項式定理:定理1.1 若A(n) = amnm+a1n+a0是一個m次多項 式，則有A(n)=(nm) 即：變量n的固定階數為m的任一多項式，與此多 項式的最高階nm同階。 證明：取n0=1,當nn0時，有 |A(n)|am|nm+|a1|n+|a0| (|am|+|am-1|/n+|a0|/nm) nm (|am|+|am-1|+|a0|) nm 令c= |am|+|am-1|+|a0| 定理得證。70 計算時間的數量級對算法有效性的影響 數量級的大小對算法的有效性有決定性的影響。 例：假設解決同一個問題的兩個算法，它們都

37、有n個輸入，計算時間的數量級分別是n2和nlogn。則： n=1024：分別需要和10240次運算。 n=2048：分別需要和22528次運算。分析：在n加倍的情況下，一個(n2)的算法計算時間增長4 倍，而一個(nlogn)算法則只用兩倍多一點的時間即 可完成。71 算法分類（計算時間）多項式時間算法：可用多項式（函數）對其計算時間限界的算法。 常見的多項式限界函數有： (1) (logn) (n) (nlogn) (n2) (n3)指數時間算法：計算時間用指數函數限界的算法 常見的指數時間限界函數： (2n) (n！) 0，則f(n)=(nm )。該定義的優點是與O的定義對稱，缺點是f(N

38、)對自然數的不同無窮子集有不同的表達式，且有不同的階時，不能很好地刻畫出f(N)的下界。比如當 100 N為正偶數 f(N)= 6N2 N為正奇數按照定義，得到f(N)=(1),這是個平凡的下界，對算法分析沒有什么價值。76定義1.3 如果存在正常數c1，c2和n0，對于所有的nn0，有c1|g(N)| |f(N)| c2|g(N)| 則記作 f(N)= (g,(N)含義：算法在最好和最壞情況下的計算時間就一個常數因子范圍內而言是相同的。可看作： 既有f(N)=(g(N)，又有f(N)=(g(N)“平均情況”限界函數7778 一個具體算法的時間復雜度和空間復雜度往往不獨立，在算法設計中要在時間

39、效率和空間效率之間折衷。非遞歸算法分析 a僅依賴于問題規模的時間復雜度 有一類簡單的問題，其操作具有普遍性，也就是說對所有的數據均等價地進行處理。6. 算法分析實例79【例1.7】交換i和j的內容。 Temp=i； i=j； j=temp； 以上三條單個語句的頻度均為1，該算法段的執行時間是一個與問題規模n無關的常數。算法的時間復雜度為常數階，記作T(n)=(1)。 如果算法的執行時間不隨著問題規模n的增加而增長，即使算法中有上千條語句,其執行時間也不過是一個較大的常數。此類算法的時間復雜度是(1)。 80【例1.8】循環次數直接依賴規模n變量計數之一。 (1) x=0;y=0; (2) fo

40、r(k=1;k=n;k+) (3) x+; (4) for(i=1;i=n;i+) (5) for(j=1;j=n;j+) (6) y+; 該算法段的時間復雜度為T(n)=(n2)。 當有若干個循環語句時，算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的頻度f(n)決定的。81【例1.9】循環次數間接依賴規模n-變量計數之二。 (1) x=1； (2) for(i=1；i=n；i+) (3) for(j=1；j=i；j+) (4) for(k=1；k=0 and Aik ) (3) i=i-1； (4) return i； 此算法的頻度不僅與問題規模n有關，還與輸入實例中A的各元素取值

41、及k的取值有關： 1. 若A中沒有與k相等的元素，則(2)頻度f(n)=n(最壞情況)； 2. 若A最后一個元素等于k ，則(2)頻度f(n)是常數1(最好情況);83 在求平均情況時，一般地假設查找不同元素的概率P是相同的,則算法的平均復雜度為： 若對于查找不同元素的概率P不相同時，其算法復雜度就只能做近似分析，或在構造更好的算法或存儲結構后，做較準確的分析。84【例1.11】求N！ 構造算法中的兩個步驟： 1）N!=N*(N-1)！(n1) 2）0!=1， 1!=1(n=0,1)。 遞歸算法如下： 以n=3為例，調用過程如下： fact(3)-fact(2)-fact(1)-fact(2)-fact(3) 遞 歸 回 溯 遞歸算法分析85【例1.11】求N！ 遞歸方程為： T(n)=T(n-1)+O(1) 其中O(1)為一次乘法操作。