算法分析與設(shè)計(jì)

1、第一章什么是算法算法是解決一個(gè)計(jì)算問題的一系列計(jì)算步驟有序、合理的排列。對一個(gè)具體問題（有確定的輸入數(shù)據(jù)）依次執(zhí)行一個(gè)正確的算法中的各操作步驟，最終將得到該問題的解（正確的輸出數(shù)據(jù)）。算法的三個(gè)要素1）.數(shù)據(jù) ：運(yùn)算序列中作為運(yùn)算對象和結(jié)果的數(shù)據(jù) ?2）.運(yùn)算 ：運(yùn)算序列中的各種運(yùn)算 ：賦值 ,算術(shù)和邏輯運(yùn)算3）.控制和轉(zhuǎn)移 ：運(yùn)算序列中的控制和轉(zhuǎn)移 .算法分類從解法上：數(shù)值型算法 ：算法中的基本運(yùn)算為算術(shù)運(yùn)算；非數(shù)值型算法：算法中的基本運(yùn)算為邏輯運(yùn)算 .從處理方式上：串行算法：串行計(jì)算機(jī)上執(zhí)行的算法；并行算法：并行計(jì)算機(jī)上執(zhí)行的算法算法的五個(gè)重要的特性（ 1） 有窮性 : 在有窮步之后結(jié)束。

2、（ 2） 確定性 : 無二義性。（ 3） 可行性 : 可通過基本運(yùn)算有限次執(zhí)行來實(shí)現(xiàn)。（ 4） 有輸入f表示存在數(shù)據(jù)處理（5） 有輸出A偽代碼程序設(shè)計(jì)語言（ PDL ），也稱為結(jié)構(gòu)化英語或者偽代碼，它是一種混合語言，它采用一種語言（例如英語）的詞匯同時(shí)采用類似另外一種語言（例如，結(jié)構(gòu)化程序語言）的語法。特點(diǎn)： 1） 使用一些固定關(guān)鍵詞的語法結(jié)構(gòu)表達(dá)了結(jié)構(gòu)化構(gòu)造、數(shù)據(jù)描述、模塊的特征；2） 以自然語言的自由語法描述了處理過程；3）數(shù)據(jù)聲明應(yīng)該既包括簡單的也包括復(fù)雜的數(shù)據(jù)結(jié)構(gòu)； 4） 使用支持各種模式的接口描述的子程序定義或者調(diào)用技術(shù)。求兩個(gè) n 階方陣的相加 C=A+B 的算法如下，分析其時(shí)間復(fù)

3、雜度。#define MAX 20/定義最大的方階void matrixadd (int n,int AMAXMAX, int BMAXMAX,i nt CMAXMAX) int i,j;for (i=0;i <n ;i+)for (j=0;j< n;j+)Cij=Aij+Bij;該算法中的基本運(yùn)算是兩重循環(huán)中最深層的語句Cij=Aij+Bij ，分析它的頻度，即 :n 1 n 11n n 1 n* n2T( n) = i 0j 0ni 0i 0=0( n2)分析以下算法的時(shí)間復(fù)雜度。void fun c(i nt n) int i=0,s=0;while (s<n) i+;

4、 s=s+i; 對于 while 循環(huán)語句，設(shè)執(zhí)行的次數(shù)為m, i 從 0 開始遞增 1 直到 m 為止，有：s=0+1+2+(m-1)=m(m-1)/2，并滿足s=m(m_1)/2<n ，則有m v n。T(n)=0( n)所以，該算法的時(shí)間復(fù)雜度為0( n )。有如下算法：void fun (int a,int n,int k) /數(shù)組 a 共有 n 個(gè)元素 int i;if (k=n-1)for (i=0;i<n;i+)/n 次prin tf("%dn",ai);else for (i=k;i<n;i+)/n-k 次ai=ai+i*i;fun (a

5、,n ,k+1);調(diào)用上述算法的語句為fun (a ,n ,0) ，求其時(shí)間復(fù)雜度。設(shè) fun(a,n,0) 的時(shí)間復(fù)雜度為T(n) , 貝 U fun(a,n,k) 的執(zhí)行時(shí)間為 T1(n,k) ，由 fun() 算法可知 :T1(n,k)=n 當(dāng) k= n-1 時(shí)T1(n,k)= (n-k)+T1(n,k+1)其他情況貝 U:T( n)=T1( n,0)=n+T1( n,1)=n+( n-1)+T1( n,2)=? =n+(n _1)+2+T1( n,n _1)=n+(n _1)+2+n=O(n2) 所以調(diào)用 fun(a,n,0) 的時(shí)間復(fù)雜度為0(n2) 。 估計(jì)如下二重循環(huán)算法在最壞情

6、況下時(shí)間復(fù)雜性T(n) 的階。for i:= 1 to n dofor j:=1 to i dos1,s2,s3,s4 ; s1,s2,s3,s4為單一賦值語句分析 ：內(nèi)循環(huán)體只需O(1) 時(shí)間，故內(nèi)循環(huán)共需漸進(jìn)分析iiNNO(1 O( 1) O()()2O(i)O( i)O(Nj 1j 1。 呼 )外循環(huán)共需 1i 1時(shí)間復(fù)雜性漸進(jìn)階分析的規(guī)則：( 最壞情況 )1).賦值，比較，算術(shù)運(yùn)算，邏輯運(yùn)算，讀寫單個(gè)變量( 常量 ) 只需1 單位時(shí)間2).執(zhí)行條件語句if c then S1 else S2的時(shí)間為TC +max(TS1,TS2).3).選擇語句case A of a1: s1 ;a2

7、: s2 ;.;am: sm需要的時(shí)間為max ( TS1,TS2 ,., TSm .4) .訪問數(shù)組的單個(gè)分量或紀(jì)錄的單個(gè)域需要一個(gè)單位時(shí)間5) .執(zhí)行 for 循環(huán)語句的時(shí)間 =執(zhí)行循環(huán)體時(shí)間 *循環(huán)次數(shù) .6). while c do s (repeat s until c)語句時(shí)間 =(Tc+Ts)循環(huán)次數(shù) .7).用 goto 從循環(huán)體內(nèi)跳到循環(huán)體末或循環(huán)后面的語句時(shí)，不需額外時(shí)間8).過程或函數(shù)調(diào)用語句：對非遞歸調(diào)用，根據(jù)調(diào)用層次由里向外用規(guī)則1-7 進(jìn)行分析 ;對遞歸調(diào)用，可建立關(guān)于T(n) 的遞歸方程 ，求解該方程得到 T(n).插入排序算法的實(shí)現(xiàn)要點(diǎn)：（1）【參數(shù)和返回值】確

8、定輸入數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù)類型，輸出個(gè)數(shù)和數(shù)據(jù)類型，數(shù)據(jù)的組織形歡迎下載2式（即邏輯結(jié)構(gòu)：線性表、樹、圖，線性表還包括棧、隊(duì)列），數(shù)據(jù)的存儲格式（數(shù)組還是鏈表），函數(shù)返回值。（2）【數(shù)據(jù)設(shè)置】變量定義與初值設(shè)定。要考慮訪問的所有數(shù)據(jù)，包括變量和常量。每個(gè)變量都要考慮它的數(shù)據(jù)類型、存儲結(jié)構(gòu)、訪問控制（局部變量、全局變量、靜態(tài)變量、公共屬性、保護(hù)屬性、私有屬性等）和初始值。（3） 【關(guān)鍵代碼】要考慮直接轉(zhuǎn)換還是需要建立相應(yīng)的獨(dú)立函數(shù)。對于賦值和下標(biāo)通?？梢灾苯愚D(zhuǎn)換。一些操作，比如數(shù)據(jù)輸入、創(chuàng)建、求長度、查找、排序、插入、刪除、顯示、修改等操作，通常需要通過建立專門的獨(dú)立函數(shù)來實(shí)現(xiàn)，也可以通過系統(tǒng)提供的命

9、令或函數(shù)來實(shí)現(xiàn)。歸并排序算法的實(shí)現(xiàn)要點(diǎn)：（1）【參數(shù)和返回值】確定輸入數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù)類型，輸出個(gè)數(shù)和數(shù)據(jù)類型，數(shù)據(jù)的組織形式（即邏輯結(jié)構(gòu)：線性表、樹、圖，線性表還包括棧、隊(duì)列），數(shù)據(jù)的存儲格式（數(shù)組還是鏈表），函數(shù)返回值。參數(shù)：序列 Apr的子序列 Apq和 Aq+1r，可以表示為區(qū)間 p,q,q,r指針（或迭代器） p, q,r： p 指向第一個(gè)子序列的首元素，q 指向第二個(gè)子序列首元素，r指向第二個(gè)子序列末尾元素之后，單個(gè)元素?cái)?shù)據(jù)長度及比較函數(shù)指針。返回值：無（2）【數(shù)據(jù)設(shè)置】變量定義與初值設(shè)定。要考慮訪問的所有數(shù)據(jù)，包括變量和常量。每個(gè)變量都要考慮它的數(shù)據(jù)類型、存儲結(jié)構(gòu)、訪問控制（局部變

10、量、全局變量、靜態(tài)變量、公共屬性、保護(hù)屬性、私有屬性等）和初始值。（3）【關(guān)鍵代碼】要考慮直接轉(zhuǎn)換還是需要建立相應(yīng)的獨(dú)立函數(shù)。對于賦值和下標(biāo)通?？梢灾苯愚D(zhuǎn)換。一些操作，比如數(shù)據(jù)輸入、創(chuàng)建、求長度、查找、排序、插入、刪除、顯示、修改等操作，通常需要通過建立專門的獨(dú)立函數(shù)來實(shí)現(xiàn)，也可以通過系統(tǒng)提供的命令或函數(shù)來實(shí)現(xiàn)。序列的劃分算法的實(shí)現(xiàn)要點(diǎn)：（1）【參數(shù)和返回值】確定輸入數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù)類型，輸出個(gè)數(shù)和數(shù)據(jù)類型，數(shù)據(jù)的組織形式（即邏輯結(jié)構(gòu)：線性表、樹、圖，線性表還包括棧、隊(duì)列），數(shù)據(jù)的存儲格式（數(shù)組還是鏈表），函數(shù)返回值。參數(shù)： A 是數(shù)組或序列 p, r 分別是整數(shù)或者迭代器返回值：分界點(diǎn)位置的整

11、數(shù)或者迭代器（2）【數(shù)據(jù)設(shè)置】變量定義與初值設(shè)定。要考慮訪問的所有數(shù)據(jù)，包括變量和常量。每個(gè)變量都要考慮它的數(shù)據(jù)類型、存儲結(jié)構(gòu)、訪問控制（局部變量、全局變量、靜態(tài)變量、公共屬性、保護(hù)屬性、私有屬性等）和初始值。（3）【關(guān)鍵代碼】要考慮直接轉(zhuǎn)換還是需要建立相應(yīng)的獨(dú)立函數(shù)。對于賦值和下標(biāo)通?？梢灾苯愚D(zhuǎn)換。一些操作，比如數(shù)據(jù)輸入、創(chuàng)建、求長度、查找、排序、插入、刪除、顯示、修改等操作，通常需要通過建立專門的獨(dú)立函數(shù)來實(shí)現(xiàn)，也可以通過系統(tǒng)提供的命令或函數(shù)來實(shí)現(xiàn)。第二章直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。分治法的設(shè)計(jì)思想：將一個(gè)難以直接解決的大問題，分割成一些規(guī)

12、模較小的相同問題，以便各個(gè)擊破，分而治之。歡迎下載3分治策略在每一層遞歸包括3 個(gè)步驟：分解 將問題分解成若干個(gè)子問題。治理 遞歸地解決各子問題。不過若子問題的規(guī)模足夠小，就以直接的方式( 不再遞歸 ) 解決子問題。合并 將子問題的解合并成原問題的一個(gè)解。divide-a nd-c onq uer(P)if ( | P | <= nO) adhoc(P);/解決小規(guī)模的問題divide P into smaller subinstances P1,P2,.,Pk； / 分解問題for (i=1,i<=k,i+)yi=divide-and-conquer(Pi); /遞歸的解各子問題

13、return merge(y1,.,yk);II 將各子問題的解合并為原問題的解分治法的復(fù)雜性分析：一個(gè)分治法將規(guī)模為n 的問題分成 k 個(gè)規(guī)模為 n/ m 的子問題去解。設(shè)分解閥值n0=1 ，且 adhoc 解規(guī)模為1 的問題耗費(fèi) 1 個(gè)單位時(shí)間。再設(shè)將原問題分解為k 個(gè)子問題以及用merge將 k 個(gè)子問題的解合并為原問題的解需用f(n) 個(gè)單位時(shí)間。用T(n) 表示該分治法解規(guī)模為T(n)n1kT( n/m)1 通過迭代法求得方程|P|=n 的問題所需的計(jì)算時(shí)間，則有:f(n) nlog m kbg m nT(n)n m的解：遞歸小結(jié)：優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng),而且容易用數(shù)學(xué)歸納法來證明

14、算法的正確性,因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲空間都比非遞歸算法<多。解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個(gè)用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來實(shí)現(xiàn)遞歸函數(shù)。3、通過變換能將一些遞歸轉(zhuǎn)化為非遞歸，從而迭代求出結(jié)果。二分搜索算法：template<class Type>int Bin arySearch(Type a, const Type & x, int l, i

15、 nt r)while (r >= l)int m = (l+r)I2;if (x = am) return m;if (x < am) r = m-1;else l = m+1;return -1;歡迎下載4算法復(fù)雜度分析：每執(zhí)行一次算法的while 循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要0(1) 時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn) 。第三章動(dòng)態(tài)規(guī)劃算法總體思想：動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。 不同

16、子問題的數(shù)目常常只有多項(xiàng)式量級。 在用分治法 求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。 如果能夠保存已解決的子問題的答案， 而在需要 時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。分治法與動(dòng)態(tài)規(guī)劃的相同點(diǎn)：分治法與動(dòng)態(tài)規(guī)劃，二者要求原問題具有最優(yōu)子結(jié)構(gòu)， 都是將問題分而治之分解成若干個(gè)規(guī)模較小的子問題 。不同點(diǎn)：分治法是將原問題分解為多個(gè)子問題， 利用遞歸對各個(gè)子問題獨(dú)立求解， 最后利用 各子問題的解進(jìn)行合并形成原問題的解。 分治法將分解后的子問題看成是相互獨(dú)立的。 動(dòng)態(tài) 規(guī)劃是將原問題分解為多個(gè)子問題， 通過計(jì)算出子問題的結(jié)果構(gòu)造一個(gè)最優(yōu)解。 動(dòng)態(tài)規(guī)劃通 過迭代法自底向

17、上求解，動(dòng)態(tài)規(guī)劃將分解后的子問題理解為相互間有聯(lián)系，有重疊的部分。knapsack 算法實(shí)現(xiàn)要點(diǎn)：(1)【參數(shù)和返回值】參數(shù)：物件個(gè)數(shù)n, 重量數(shù)組W ( 一維整型) ，價(jià)值數(shù)組C ( 一維整型) ，背包容量C ( 整型 ) 。返回值：返回整型二維數(shù)組m(2) 【數(shù)據(jù)設(shè)置】設(shè)置一個(gè) ( n+1 ) x( c+1 ) 二維數(shù)表 m; 循環(huán)控制變量 i, j ( 整數(shù) )(3) 【關(guān)鍵代碼】偽代碼結(jié)構(gòu)清晰，容易實(shí)現(xiàn)。Floyd 算法實(shí)現(xiàn)要點(diǎn)：(1)【參數(shù)和返回值】參數(shù)：圖的頂點(diǎn)個(gè)數(shù)n; 圖的鄰接矩陣：浮點(diǎn)型矩陣w;返回值：返回矩陣D 和 n 構(gòu)成的數(shù)據(jù)結(jié)構(gòu)(2)【數(shù)據(jù)設(shè)置】兩個(gè)二維數(shù)表d 和 pi

18、 ( 對應(yīng)矩陣 D 和 n ); 循環(huán)控制變量 i,j,k ( 整數(shù) )(3)【關(guān)鍵代碼】頂點(diǎn)從0? n-1 編號。鄰接矩陣D 中 R 用浮點(diǎn)型最大值代替；父結(jié)點(diǎn)矩陣n 中空指針 NIL 用 -1 表示；要輸出路徑還需要實(shí)現(xiàn)PRINT-ALL-PAIRS-SHORTEST-PA算法第四章：貪心算法：依賴于當(dāng)前已經(jīng)做出的所有選擇，采用自頂向下 ( 每一步根據(jù)策略得到當(dāng)前一個(gè)最優(yōu)解，保證每一步都是選擇當(dāng)前最優(yōu)的) 的解決方法。貪婪算法設(shè)計(jì)的 3 個(gè)步驟：( 1 ) 分析問題的最優(yōu)子結(jié)構(gòu)( 2) 分析問題的貪婪選擇性質(zhì)( 3 ) 根據(jù)最優(yōu)子結(jié)構(gòu)和貪婪性質(zhì)自頂向下計(jì)算最優(yōu)解。Huffman 算法實(shí)現(xiàn)要

19、點(diǎn)：(1)【參數(shù)和返回值】參數(shù)：字符集C 及頻數(shù)數(shù)組及個(gè)數(shù)；返回值：返回二叉樹(2)【數(shù)據(jù)設(shè)置】需要最小優(yōu)先隊(duì)列Q; 循環(huán)控制變量 i ( 整數(shù) )(3) 【關(guān)鍵代碼】需要先實(shí)現(xiàn)二叉樹的數(shù)據(jù)結(jié)構(gòu)歡迎下載5單源最短路徑算法實(shí)現(xiàn)要點(diǎn)( 與prim 算法類似 ) ：(1)【參數(shù)和返回值】參數(shù)：圖形矩陣W ( 浮點(diǎn)型 ) 及頂點(diǎn)數(shù)n( 整型 ) 及源點(diǎn) s ( 整型 )返回值：返回key 和 pi 的數(shù)據(jù)結(jié)構(gòu)(2)【數(shù)據(jù)設(shè)置】需要浮點(diǎn)型數(shù)組d 和整型數(shù)組 pi, 需要最小優(yōu)先隊(duì)列 Q; 需要頂點(diǎn)變量 u 和 v ( 整數(shù) )（ 3）【關(guān)鍵代碼】需要先實(shí)現(xiàn)動(dòng)態(tài)優(yōu)先隊(duì)列廣度優(yōu)先搜索 BFS 算法實(shí)現(xiàn)要點(diǎn)：

20、（1） 【參數(shù)和返回值】數(shù)據(jù)類型：圖的鄰接表數(shù)組adj 和圖的頂點(diǎn)個(gè)數(shù)n, 隊(duì)列操作過程：隊(duì)列的創(chuàng)建、判空、入隊(duì)、出隊(duì)，隊(duì)列需要指向隊(duì)首和隊(duì)尾的指針head 和 trail參數(shù)：鄰接表表示的圖g 和源點(diǎn) s；返回值：返回?cái)?shù)組和 d 構(gòu)成的數(shù)據(jù)結(jié)構(gòu)（2） 【數(shù)據(jù)設(shè)置】為了提高可讀性，定義枚舉類型Color ，包含顏色WHITE 、GRAY 和 BLACK 聲明隊(duì)列 Q，表示計(jì)算結(jié)果數(shù)組color （枚舉類型）、 d （整型）和 pi （整型）；臨時(shí)變量u 和 v （整型）（3） 【關(guān)鍵代碼】頂點(diǎn)從0? n-1 編號。最短路徑距離d 中 a 用整型最大值 INT_MAX 代替; 父結(jié)點(diǎn)數(shù)組；中空指

21、針NIL 用-1 表示；要輸出路徑還需要實(shí)現(xiàn)PRINT-PATH算法深度優(yōu)先搜索 DFS 算法實(shí)現(xiàn)要點(diǎn)：（1） 【參數(shù)和返回值】數(shù)據(jù)類型：圖的鄰接表數(shù)組adj 和圖的頂點(diǎn)個(gè)數(shù)n, 棧操作過程：棧的創(chuàng)建、判空、入棧、出棧，棧需要指向棧頂和棧底的指針top 和 bottom參數(shù)：鄰接表表示的圖g 和源點(diǎn) s; 返回值：返回?cái)?shù)組， d 和 f 構(gòu)成的數(shù)據(jù)結(jié)構(gòu)（2） 【數(shù)據(jù)設(shè)置】為了提高可讀性，定義枚舉類型Color , 包含顏色WHITE 、GRAY 和 BLACK 聲明棧 S,表示計(jì)算結(jié)果數(shù)組 color （枚舉類型）、 d （整型）、 f （整型）和 pi （整型）臨時(shí)變量 u, v 和 s （

22、整型）（3）【關(guān)鍵代碼】頂點(diǎn)從0? n-1 編號。父結(jié)點(diǎn)數(shù)組；中空指針NIL 用-1 表示；需要考慮如何實(shí)現(xiàn)第13 行： if v Adju a nd colorv = WHITE第十章泛型程序設(shè)計(jì)的主要思想將算法從特定的數(shù)據(jù)結(jié)構(gòu)中抽象出來，成為通用的、可以作用于各種不同的數(shù)據(jù)結(jié)構(gòu)。概念（ concept ）：用來界定具備一定功能的數(shù)據(jù)類型，如“支持< 運(yùn)算符”的數(shù)據(jù)類型構(gòu)成 Comparable這一概念；模型（ model ）：符合一個(gè)概念的數(shù)據(jù)類型稱為該概念的模型，如int 型是 Comparable 概念的模型。STL 就是建立在模板函數(shù)和模板類基礎(chǔ)之上的功能強(qiáng)大的庫模板函數(shù)可以實(shí)

23、現(xiàn)一般化的常用算法（如統(tǒng)計(jì)、排序、查找等）模板類可以實(shí)現(xiàn)支持幾乎所有類型的容器，用來實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)（如鏈表、棧、隊(duì)列、平衡二叉樹等）STL 頭文件一覽| 頭文件內(nèi)容頭文件內(nèi)春<iterator>迭代器<vector>向屋<utilrty>輔助功能<deque>雙頭駅列<memo ry>內(nèi)存管理鏈表<algorrthm><set><functional>雷數(shù)對象<map>映射勺務(wù)重映射<numeric>數(shù)值運(yùn)算<stack><queue>隊(duì)列與優(yōu)先隊(duì)列歡迎