1、 算法設(shè)計(jì)與分析ECNUYinping LiuECNUYinping Liu課程目標(biāo)通過對常用的、有代表性的算法的研究，讓學(xué)生理解并掌握算法設(shè)計(jì)的基本技術(shù)。培養(yǎng)學(xué)生分析算法復(fù)雜度的初步能力，鍛煉其邏輯思維能力和想象力，并使之了解算法理論的發(fā)展。鼓勵(lì)學(xué)生運(yùn)用算法知識(shí)解決實(shí)際問題，培養(yǎng)他們的獨(dú)立科研能力和理論聯(lián)系實(shí)踐的能力。參考教材1. 算法設(shè)計(jì)技巧與分析 吳偉昶 方世昌 等譯 電子工業(yè)出版社2. 算法設(shè)計(jì)與分析基礎(chǔ) (影印版) 美 Anany Levitin 著3. 數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C+語言描述. Sartaj Sahni著. 汪詩林，孫曉東等譯. 機(jī)械工業(yè)出版社. 2000年1月第1版 主

2、要內(nèi)容介紹 第1章算法引論 第2章 矩陣計(jì)算 第3章遞歸與分治策略 第4章動(dòng)態(tài)規(guī)劃 第5章貪心算法 第6章回溯法 第7章隨機(jī)概率算法 第8章 計(jì)算幾何學(xué) 第9章 NP 完全性理論主要內(nèi)容介紹（續(xù)） 第1章 算法引論本章主要知識(shí)點(diǎn)：1.1算法與程序1.2表達(dá)算法的抽象機(jī)制1.3描述算法1.4算法復(fù)雜性分析 1.1算法與程序算法：是滿足下述性質(zhì)的指令序列。輸 入：有零個(gè)或多個(gè)外部量作為算法的輸入。 輸 出：算法產(chǎn)生至少一個(gè)量作為輸出。 確定性：組成算法的每條指令清晰、無歧義。 有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行 每條指令的時(shí)間也有限。程序：是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。 程序可以不滿

3、足算法的性質(zhì)(4)即有限性。1.2表達(dá)算法的抽象機(jī)制1.從機(jī)器語言到高級語言的抽象高級程序設(shè)計(jì)語言的主要好處是：（1）高級語言更接近算法語言，易學(xué)、易掌握，一般工程技術(shù)人員只需 要幾周時(shí)間的培訓(xùn)就可以勝任程序員的工作；（2）高級語言為程序員提供了結(jié)構(gòu)化程序設(shè)計(jì)的環(huán)境和工具，使得設(shè)計(jì) 出來的程序可讀性好，可維護(hù)性強(qiáng)，可靠性高；（3）高級語言不依賴于機(jī)器語言，與具體的計(jì)算機(jī)硬件關(guān)系不大，因而 所寫出來的程序可植性好、重用率高；（4）把繁雜瑣碎的事務(wù)交給編譯程序，所以自動(dòng)化程度高，開發(fā)周期短， 程序員可以集中時(shí)間和精力從事更重要的創(chuàng)造性勞動(dòng)，提高程序質(zhì)量。1.2表達(dá)算法的抽象機(jī)制2.抽象數(shù)據(jù)類型抽象

4、數(shù)據(jù)類型是算法的一個(gè)數(shù)據(jù)模型連同定義在該模型上并作為算法構(gòu)件的一組運(yùn)算。 抽象數(shù)據(jù)類型帶給算法設(shè)計(jì)的好處有： （1）算法頂層設(shè)計(jì)與底層實(shí)現(xiàn)分離；（2）算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)隔開，允許數(shù)據(jù)結(jié)構(gòu)自由選擇；（3）數(shù)據(jù)模型和該模型上的運(yùn)算統(tǒng)一在ADT中,便于空間和時(shí)間耗費(fèi)折衷；（4）用抽象數(shù)據(jù)類型表述的算法具有很好的可維護(hù)性；（5）算法自然呈現(xiàn)模塊化；（6）為自頂向下逐步求精和模塊化提供有效途徑和工具；（7）算法結(jié)構(gòu)清晰，層次分明，便于算法正確性的證明和復(fù)雜性的分析。1.3 復(fù)雜性分析初步程序性能 (program performance) 是指運(yùn)行一個(gè)程序所需的內(nèi)存大小和時(shí)間多少。所以，程序的性能一

5、般指程序的空間復(fù)雜性和時(shí)間復(fù)雜性。性能評估主要包含兩方面, 即性能分析(performance analysis)與性能測量 (performance measurement), 前者采用分析的方法，后者采用試驗(yàn)的方法?？紤]空間復(fù)雜性的理由在多用戶系統(tǒng)中運(yùn)行時(shí)，需指明分配給該程序的內(nèi)存大小；想預(yù)先知道計(jì)算機(jī)系統(tǒng)是否有足夠的內(nèi)存來運(yùn)行該程序；一個(gè)問題可能有若干個(gè)不同的內(nèi)存需求解決方案,從中擇取;用空間復(fù)雜性來估計(jì)一個(gè)程序可能解決的問題的最大規(guī)模。 考慮時(shí)間復(fù)雜性的理由某些計(jì)算機(jī)用戶需提供程序運(yùn)行時(shí)間的上限(用戶可接受的);所開發(fā)的程序需要提供一個(gè)滿意的實(shí)時(shí)反應(yīng)。選取方案的規(guī)則： 如果對于解決一個(gè)

6、問題有多種可選的方案，那么方案的選取要基于這些方案之間的性能差異。對于各種方案的時(shí)間及空間的復(fù)雜性，最好采取加權(quán)的方式進(jìn)行評價(jià)。但是隨著計(jì)算機(jī)技術(shù)的迅速發(fā)展，對空間的要求往往不如對時(shí)間的要求那樣強(qiáng)烈。因此我們這里的分析主要強(qiáng)調(diào)時(shí)間復(fù)雜性的分析。 1 空間復(fù)雜性程序所需要的空間： 指令空間-用來存儲(chǔ)經(jīng)過編譯之后的程序指令。程序所需的指令空間的大小取決于如下因素： 把程序編譯成機(jī)器代碼的編譯器； 編譯時(shí)實(shí)際采用的編譯器選項(xiàng)； 目標(biāo)計(jì)算機(jī)。 數(shù)據(jù)空間-用來存儲(chǔ)所有常量和變量的值。分成兩部分： a.) 存儲(chǔ)常量和簡單變量； b.) 存儲(chǔ)復(fù)合變量。前者所需的空間取決于所使用的計(jì)算機(jī)和編譯器，以及變量與常

7、量的數(shù)目，這是由于我們往往是指計(jì)算所需內(nèi)存的字節(jié)數(shù)，而每個(gè)字節(jié)所占的數(shù)位依賴于具體的機(jī)器環(huán)境。后者包括數(shù)據(jù)結(jié)構(gòu)所需的空間及動(dòng)態(tài)分配的空間。 類型 占用字節(jié)數(shù) 適用范圍 char 1 -128127 unsigned char 1 0 255 short 2 -32768-32767 int 2 -32768-32767 unsigned int 2 0-65535 long 4 -231- 231-1 unsigned long 4 0- 231-1 float 4 3.4E 38 double 8 1.7E 308 pointer 2計(jì)算方法：結(jié)構(gòu)變量所占空間等于各個(gè)成員所占空間的累加；數(shù)組

8、變量所占空間等于數(shù)組大小乘以單個(gè)數(shù)組元素所占的空間。 例如： double a100; 所需空間為： 100 8=800 int matrixrc; 所需空間為 2rc 環(huán)境棧空間-保存函數(shù)調(diào)用返回時(shí)恢復(fù)運(yùn)行所需要的信息。當(dāng)一個(gè)函數(shù)被調(diào)用時(shí)，下面數(shù)據(jù)將被保存在環(huán)境棧中： 返回地址；所有局部變量的值、遞歸函數(shù)的傳值形式參數(shù)的值；所有引用參數(shù)以及常量引用參數(shù)的定義。在分析空間復(fù)雜性中，實(shí)例特征的概念特別重要。所謂實(shí)例特征是指決定問題規(guī)模的那些因素。如，輸入和輸出的數(shù)量或相關(guān)數(shù)的大小，如對 n 個(gè)元素進(jìn)行排序、nn矩陣的加法等。都可以 n 作為實(shí)例特征， 兩個(gè) mn 矩陣的加法應(yīng)該以n 和 m 兩個(gè)

9、數(shù)作為實(shí)例特征。一個(gè)程序所需要的空間可分為兩部分：固定部分，它獨(dú)立于實(shí)例特征。主要包括指令空間、簡單變量以及定義復(fù)合變量所占用的空間、常量所占用的空間?？勺儾糠郑饕◤?fù)合變量所需的空間（其大小依賴于所解決的具體問題）。動(dòng)態(tài)分配的空間（依賴于實(shí)例特征）、遞歸棧所需的空間（依賴于實(shí)例特征）。 令 S(P)表示程序 P 所需的空間，則有 S(P）=c+Sp(實(shí)例特征)其中 c 表示固定部分所需要的空間，是一個(gè)常數(shù)； Sp 表示可變部分所需的空間。在分析程序的空間復(fù)雜性時(shí)，一般著重于估算Sp(實(shí)例特征)。實(shí)例特征的選擇一般受到相關(guān)數(shù)的數(shù)量以及程序輸入和輸出規(guī)模的制約。 注：一個(gè)精確的分析還應(yīng)當(dāng)包括

10、編譯期間所產(chǎn)生的臨時(shí)變量所需的空間，這種空間與編譯器直接相關(guān)聯(lián)，在遞歸程序中除了依賴于遞歸函數(shù)外，還依賴于實(shí)例特征。但是，在考慮空間復(fù)雜性時(shí)，一般都被忽略。例子：例1 利用應(yīng)用參數(shù) Template T abc( T &a, T &b, T &c)Return a+b+c+bc+(a+b+c)/(a+b)+4;在例1中，采用 T 作為實(shí)例特征。由于 a,b,c 都是引用參數(shù)，在函數(shù)中不需要為它們的值分配空間，但需保存指向這些參數(shù)的指針。若每個(gè)指針需要2 個(gè)字節(jié)，則共需要6個(gè)字節(jié)的指針空間，此時(shí)函數(shù)所需要的總空間是一個(gè)常量，而 Sabc(實(shí)例特征)=0。 但若函數(shù) abc 的參數(shù)是傳值參數(shù)，則每

11、個(gè)參數(shù)需要分配空間 sizeof(T) 的空間，于是 a,b,c 所需的空間為：3 sizeof(T). 函數(shù) abc 所需要的其他空間都與 T 無關(guān)，故Sabc(實(shí)例特征)= 3 sizeof(T)。 如果假定使用a,b,c 的大小作為實(shí)例特征，由于在傳值參數(shù)的情形下，分配給每個(gè)變量 a, b, c 的空間均為 sizeof(T), 而不考慮這些變量中的實(shí)際值是多大，所以，不論是用引用參數(shù)還是使用傳值參數(shù)，都有Sabc(實(shí)例特征)= 0。例2 順序搜索 template int SequentialSearch(T a,const T &x, int n) / 在 a0:n-1中搜索x，若找

12、到則回所在的位置，否則返回-1 int i; for(i=0; in & ai!=x; i+); if (i=n) return 1; return i; 在例2中，假定采用被查數(shù)組的長度 n 作為實(shí)例特征，并取T 為 int 類型。數(shù)組中每個(gè)元素需要 2 個(gè)字節(jié)，實(shí)參x 需要2 個(gè)字節(jié)，傳值形式參數(shù) n 需要2 個(gè)字節(jié)，局部變量 i 需要2 個(gè)字節(jié)，整數(shù)常量 1 需要2 個(gè)字節(jié)，所需要的總的數(shù)據(jù)空間為 10 個(gè)字節(jié)，其獨(dú)立于 n, 所以 S順序查找(n)=0. 這里我們并沒有把數(shù)組a 所需的空間計(jì)算進(jìn)來，因?yàn)樵摂?shù)組所需的空間已在定義實(shí)際參數(shù)(對應(yīng)于 a) 的函數(shù)中分配，不能再加到函數(shù) Seq

13、uentialSearch 所需的空間上去。 2 時(shí)間復(fù)雜性時(shí)間復(fù)雜性的構(gòu)成 一個(gè)程序所占時(shí)間 T(P)=編譯時(shí)間+運(yùn)行時(shí)間； 編譯時(shí)間與實(shí)例特征無關(guān)，而且，一般情況下，一個(gè)編譯過的程序可以運(yùn)行若干次，所以，人們主要關(guān)注的是運(yùn)行時(shí)間，記作 tp(實(shí)例特征）； 如果了解所用編譯器的特征，就可以確定代碼 P 進(jìn)行加、減、乘、除、比較、讀、寫等所需的時(shí)間，從而得到計(jì)算 tp 的公式。令 n 代表實(shí)例特征（這里主要是問題的規(guī)模），則有如下的計(jì)算公式： tp(n)=caADD(n)+csSUB(n)+cmMUL(n)+cdDIV(n)+ccCMP(n)+其中，ca，cs，cm，cd，cc 分別表示一次加

14、、減、乘、除及比較操作所需的時(shí)間，函數(shù) ADD, SUB, MUL, DIV, CMP 分別表示代碼 P 中所使用的加、減、乘、除及比較操作的次數(shù)； 一個(gè)算術(shù)操作所需的時(shí)間取決于操作數(shù)的類型(int, float, double 等等），所以，有必要對操作按照數(shù)據(jù)類型進(jìn)行分類； 在構(gòu)思一個(gè)程序時(shí)，影響 tp的許多因素還是未知的，所以，在多數(shù)情況下僅僅是對 tp 進(jìn)行估計(jì)。估算運(yùn)行時(shí)間的方法： A. 找一個(gè)或多個(gè)關(guān)鍵操作，確定這些關(guān)鍵操作所需要的執(zhí)行時(shí)間（對于前面所列舉的四種運(yùn)算及比較操作，一般被看作是基本操作，并約定所用的時(shí)間都是一個(gè)單位）； B. 確定程序總的執(zhí)行步數(shù)。 操作計(jì)數(shù)首先選擇一種

15、或多種操作（如加、乘和比較等），然后計(jì)算這些操作分別執(zhí)行了多少次。關(guān)鍵操作對時(shí)間復(fù)雜性影響最大。 例3 尋找最大元素 template int Max(T a,int n) /尋找 a0:n-1中的最大元素 int pos=0; for(i=1; in; i+) if(aposai) pos=i; return pos; 這里關(guān)鍵操作是比較。For 循環(huán)中共進(jìn)行了n-1 次比較。Max 還執(zhí)行了其它比較，如 for 循環(huán)每次執(zhí)行之前都要比較一下i和n.此外，Max 還進(jìn)行了其它的操作，如初始化 pos、循環(huán)控制變量i的增量。這些一般都不包含在估算中，若納入計(jì)數(shù)，則操作計(jì)數(shù)將增加一個(gè)常量。 例4

16、 n 次多項(xiàng)式求值 template T PolyEval(T coeff, int n, const T& x) / 計(jì)算 n 次多項(xiàng)式的值， coeff0:n 為多項(xiàng)式的系數(shù) T y=1, value=coeff0; for(i=1;i=n;i+) /n 循環(huán) / 累加下一項(xiàng) y=x; /一次乘法 value+=ycoeffi; /一次加法和一次乘法 return value; / 3n 次基本操作 例5 例6 template templatevoid Rank(T a,int n,int r) void SelectionSort(T a,int n) /計(jì)算 a0:n-1 中元素的排

17、名 / 對數(shù)組 a0:n-1 中元素排序 for(int i=1; i1;size-) ri=0; /初始化 j=Max(a, size); / 逐對比較所有的元素 Swap(aj,asize-1); for(int i=1;in;i+) for (j=0;ji;j+) if (ajai) ri+; / 其中函數(shù) Max 定義如例3 else rj+； /函數(shù)Swap 由下述給出 template inline void Swap(T &a, T &b) T temp=a; a=b; b=temp; 在這兩個(gè)程序中，關(guān)鍵的操作是比較。 在例5中，對每個(gè)i 的取值，執(zhí)行比較的次數(shù)是i,總的比較次

18、數(shù)為 1+2+(n-1)=(n-1)n/2. 在此，for循環(huán)的額外開銷、初始化數(shù)組r的開銷、以及每次比較 a 中的兩個(gè)數(shù)時(shí)對r 進(jìn)行的增值開銷都未列入其中。 在例6給出的排序中，首先找出最大元素，把它移動(dòng)到an-1,然后在余下的 n-1 個(gè)中再尋找最大的元素，并把它移動(dòng)到an-2,如此進(jìn)行下去，此種方法稱為選擇排序(selection sort). 從例3中已經(jīng)知道，每次調(diào)用 Max(a,size)需要進(jìn)行size-1 次比較，所以總的比較次數(shù)為1+2+n-1=(n-1)n/2. 每調(diào)用一次函數(shù) Swap需要執(zhí)行三次元素移動(dòng)，所以總的移動(dòng)次數(shù)為 3(n-1). 當(dāng)然，在本程序中，還會(huì)有其他開

19、銷，在此未予考慮。 注：人們往往還會(huì)關(guān)心最好的、最壞的和平均的操作步數(shù)是多少。在上面的計(jì)算中我們都考慮的是最壞的情況。執(zhí)行步數(shù) 利用操作計(jì)數(shù)方法估計(jì)程序的時(shí)間復(fù)雜性注意力集中在“關(guān)鍵操作”上，忽略了所選擇操作之外其它操作的開銷。下面所要講的統(tǒng)計(jì)執(zhí)行步數(shù)（step-count)的方法則要統(tǒng)計(jì)程序/函數(shù)中所有部分的時(shí)間開銷。執(zhí)行步數(shù)也是實(shí)例特征的函數(shù)。通常做法是選擇一些感興趣的實(shí)例特征。如，要了解程序的運(yùn)行時(shí)間是如何隨著輸入數(shù)據(jù)的個(gè)數(shù)增加而增加的，則把執(zhí)行步數(shù)僅看作輸入數(shù)據(jù)個(gè)數(shù)的函數(shù)。所謂程序步是一個(gè)語法或語義上的程序片斷，該片斷的執(zhí)行時(shí)間獨(dú)立于實(shí)例特征。例如語句：return a+b+b*c+(

20、a+b+c)/(a+b)+4; 和 x=y; 都可以作為程序步。一種直觀的統(tǒng)計(jì)程序執(zhí)行步數(shù)的方法是做執(zhí)行步數(shù)統(tǒng)計(jì)表.矩陣加法程序執(zhí)行步數(shù)統(tǒng)計(jì)表 語句 s/e 頻率 總步數(shù) Void Addm(T*a, ) 0 0 0 0 0 0 for(int i=0;irows;i+) 1 rows+1 rows+1 for(int j=0;j=0。漸近符號O的定義：f(n)=O(g(n)當(dāng)且僅當(dāng)存在正的常數(shù)c 和n0，使得對于所有的n=n0，有f(n)=cg(n)。此時(shí)，稱g(n)是f(n)的一個(gè)上界。函數(shù)f 至多是函數(shù)g 的c 倍，除非 nn0 。即是說，當(dāng)n 充分大時(shí)，g 是f的一個(gè)上界函數(shù)，在相差一

21、個(gè)非零常數(shù)倍的情況下。通常情況下，上界函數(shù)取單項(xiàng)的形式，如表1 所列。C0=O(1): f(n) 等于非零常數(shù)的情形。3n+2=O(n): 可取c4，n02。100n+6=O(n): 可取c=101，n06。10n2+4n+3=O(n2): 可取 c=11, n0662n+n2=O(2n): 可取c =7，n0=4.3log n + 2n + n2 =O(n2).nlog n +n2=O(n2).3n+2=O(n2).注意事項(xiàng)1.用來作比較的函數(shù)g(n)應(yīng)該盡量接近所考慮的函數(shù)f(n).3n+2=O(n2) 松散的界限；3n+2=O(n) 較好的界限。2.不要產(chǎn)生錯(cuò)誤界限。n2+100n+6，

22、當(dāng)n3 時(shí)，n2+100n+6c-100 就有n2+100n+6cn。同理，3n2+42n=O(n2)是錯(cuò)誤的界限。3.f(n)=O(g(n)不能寫成g(n)=O(f(n)，因?yàn)閮烧卟⒉坏葍r(jià)。實(shí)際上，這里的等號并不是通常相等的含義。按照定義，用集合符號更準(zhǔn)確些：O(g(n)=f(n)|f(n)滿足：存在正的常數(shù)c 和n0，使得當(dāng)n=n0 時(shí)，f(n)=cg(n)。所以，人們常常把f(n)=O(g(n)讀作：“f(n)是g(n)的一個(gè)大O 成員”。大O比率定理：對于函數(shù) f(n) 和 g(n) ,如果極限 存在,則f(n)= O(g(n).當(dāng)且僅當(dāng)存在正的常數(shù)c,使得例子 因?yàn)?所以 3n+2=O(n); 因?yàn)?所以 10n2+4n+2=O(n2); 因?yàn)?所以 62n+n2=O(2n); 因?yàn)?所以 n16+3n2=O(2n);本例最后一個(gè)不是一個(gè)好的上界估計(jì)，問題出在極限值不是正的常數(shù)。例如, 根據(jù)上述定理， 我們很容易得出：符號的定義(f(n)= (g(n) 當(dāng)且僅當(dāng)存在正的常數(shù)c 和 n0 ，使得對于所有的n n0 ，有f(n) c(g(n) 。此時(shí)，稱g(n)是f(n)的一個(gè)下界。函數(shù)f 至少是函數(shù)g 的c 倍，除非n 0,則 小o 符號定義： f(n)= o (g(n) 當(dāng)且僅當(dāng)f