計(jì)算機(jī)算法基礎(chǔ)

1、2024/3/17,計(jì)算機(jī)算法基礎(chǔ),周中成蘇州科技學(xué)院應(yīng)用數(shù)學(xué)系,2024/3/17,序,先修課：高等數(shù)學(xué)高等代數(shù)程序設(shè)計(jì)——使用高級(jí)程序語(yǔ)言描述一個(gè) 具體算法的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)——為表達(dá)非數(shù)值算法提供了抽 象的運(yùn)算機(jī)制,,,數(shù)學(xué)類,計(jì)算機(jī)類,2024/3/17,,如何編寫計(jì)算機(jī)程序：數(shù)據(jù)結(jié)構(gòu)+算法 = 程序算法：計(jì)算機(jī)軟件的“靈魂”

2、 結(jié)論：算法是計(jì)算機(jī)科學(xué)和計(jì)算機(jī)應(yīng)用的核心，圖靈獎(jiǎng)得主Donald E. Knuth說：”計(jì)算機(jī)科學(xué)就是算法的研究“,2024/3/17,教材： 算法分析與設(shè)計(jì) 劉任任主編 武漢理工大學(xué)出版社 參考書： 算法設(shè)計(jì)技巧與分析 [沙特]M.H.Alsuwaiyel 電子工業(yè)出版社Introduction to The Design & Analysis of Al

3、gorithms(算法設(shè)計(jì)與分析基礎(chǔ))（影印版） [美] Anany Levitin 算法設(shè)計(jì)與分析 王曉東編著 清華大學(xué)出版社 計(jì)算機(jī)算法導(dǎo)引——設(shè)計(jì)與分析 盧開澄編著 清華大學(xué)出版社 Introduction To Algorithm 高教出版社，MIT Press 學(xué)時(shí)：51學(xué)時(shí),2024/3/17,章節(jié)安排,第一章 導(dǎo)論 √第二章 分治與遞歸

4、 √第三章 貪心算法 √第四章 動(dòng)態(tài)規(guī)劃 √第五章 回溯法 ⊙第六章 分枝-限界法 ⊙第八章 NP完全問題 ?,2024/3/17,第一章 引論,§1.1 算法的定義及特性1. 什么是算法（algorithm）

5、算法如數(shù)學(xué)、計(jì)算一樣，是一個(gè)基本概念。 ★ Webster辭典：“algorithm（算法）在有限步驟內(nèi)解一個(gè)數(shù)學(xué)問題的過程，步驟中常常包括某一操作的重復(fù)。更廣義地說，一個(gè)算法就是為解一個(gè)問題或?qū)崿F(xiàn)某一目標(biāo)的逐步過程“ ★D.E.Knuth說：一個(gè)算法就是一個(gè)有窮規(guī)則的集合，其中的規(guī)則規(guī)定了一個(gè)解決某一特定類型的問題的運(yùn)算序列。此外，它還具有下面第二部分所述的5個(gè)重要特征,2024/3/17,2.

6、算法的五個(gè)重要特性 有窮性、確定性、可行性、輸入、輸出,1）確定性：算法的每種運(yùn)算必須要有確切的定義，不能有二義性。 例：菜譜就不是一個(gè)算法，因?yàn)椴俗V中經(jīng)常有這樣的步驟：“加入食鹽少許”，這種“少許”是不確定的。,2024/3/17,2）可行性 算法中有待實(shí)現(xiàn)的運(yùn)算都是基本的運(yùn)算，原理上每種運(yùn)算都能由人用紙和筆在“有限”的時(shí)間內(nèi)完成。,2024/3/17,3）輸入 每個(gè)算法有0個(gè)或多個(gè)輸入。這

7、些輸入是在算法開始之前給出的量，取自于特定的對(duì)象集合——定義域（或值域）,4）輸出 一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，這些輸出是同輸入有某種特定關(guān)系的量。,2024/3/17,5）有窮性 一個(gè)算法總是在執(zhí)行了有窮步的運(yùn)算之后終止。 3。計(jì)算過程與算法 只滿足確定性、能行性、輸入、輸出四個(gè)特性的一組規(guī)則。 算法和計(jì)算過程的區(qū)別： 計(jì)算過程：操作系統(tǒng)(不終止的運(yùn)行過程) 算法是“可以

8、終止的計(jì)算過程” 算法的時(shí)效性：只能把在相當(dāng)有窮步內(nèi)終止的算法投 入到計(jì)算機(jī)上運(yùn)行,2024/3/17,4。程序與算法,二者關(guān)系：程序可以用來(lái)描述算法，同一個(gè)算法可以用不同語(yǔ)言（c, basic, 匯編）編寫的程序來(lái)描述。 程序不一定是算法，因?yàn)樗灰欢ǚ纤惴ǖ?條性質(zhì)，如操作系統(tǒng)作為整體是程序，但不是一個(gè)算法，因?yàn)椴僮飨到y(tǒng)是無(wú)限循環(huán)的過程,2024/

9、3/17,5. 我們的主要任務(wù) 算法學(xué)習(xí)將涉及5個(gè)方面的內(nèi)容： 1）設(shè)計(jì)算法：創(chuàng)造性的活動(dòng) 2）表示算法：思想的表示形式：類C語(yǔ)言、SPARKS語(yǔ)言（類PASCAL語(yǔ) 言） 3）確認(rèn)算法：證明算法對(duì)所有可能的合法輸入都能得出正確的答案。 算法

10、證明：證明算法的正確性，與語(yǔ)言無(wú)關(guān) 程序證明：證明程序的正確性 4）分析算法：對(duì)算法的時(shí)、空特性做定量分析，以了解算法的好壞 5）測(cè)試程序： 調(diào)試：“調(diào)試只能指出有錯(cuò)誤，而不能指出它們不存在錯(cuò)誤”

11、 作時(shí)空分布圖：驗(yàn)證分析結(jié)論，優(yōu)化算法設(shè)計(jì) 本課程集中于學(xué)習(xí)算法的設(shè)計(jì)與分析。通過學(xué)習(xí)，掌握計(jì)算機(jī)算法設(shè)計(jì)和分析基本策略與方法，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ),2024/3/17,6. 課程關(guān)系 數(shù)據(jù)結(jié)構(gòu) 程序設(shè)計(jì)語(yǔ)言：結(jié)構(gòu)化設(shè)計(jì) 數(shù)學(xué)基礎(chǔ) 非數(shù)值計(jì)算領(lǐng)域的基本知識(shí),2024/3/17,§1.2 分析算法,分析算法的目的及歷史背景目的：通過對(duì)算法的分析，在把算法變成程序

12、實(shí)際運(yùn)行前，就知道為完成一項(xiàng)任務(wù)所設(shè)計(jì)的算法（主要在時(shí)空效率方面）的好壞，從而選擇好的算法，改進(jìn)差的算法。歷史背景：算法分析是計(jì)算機(jī)領(lǐng)域的“古老”而“前沿”的課題。稱為計(jì)算復(fù)雜性問題，屬于計(jì)算理論的一個(gè)重要領(lǐng)域，它是由于對(duì)有效算法的需求而發(fā)展起來(lái)的，產(chǎn)生于二十世紀(jì)六十年代，繁榮于七、八十年代。,2024/3/17,算法分析的標(biāo)準(zhǔn),1。正確性(Correctness)2。簡(jiǎn)潔、清晰(Simplicity) 一般而言（并

13、不必然如此），最簡(jiǎn)單、思路最直接的解決方法效率往往不是最佳的。然而，簡(jiǎn)潔性也是一個(gè)算法值得追求的目標(biāo)。它可以使驗(yàn)證算法的正確性相對(duì)容易，它也使我們編寫、調(diào)試、修改程序更為容易。當(dāng)然，若程序使用頻率很高，算法的效率還是選擇算法的決定性因素。3。優(yōu)化性(Optimality)符合優(yōu)化性的算法不是已知中最好的（the best known），而是解決問題的一切可能算法中最好的(the best possible)。4?？臻g復(fù)雜度(Spa

14、ce Complexity)5。時(shí)間復(fù)雜性,2024/3/17,如何衡量時(shí)間復(fù)雜性,算法（程序）實(shí)際執(zhí)行時(shí)間,程序中的指令或語(yǔ)句的執(zhí)行次數(shù)（頻率計(jì)數(shù)）,受運(yùn)行機(jī)器性能的影響,——缺陷：,——缺陷：,高度依賴于編程語(yǔ)言及程序員的編程風(fēng)格，并要首先編寫調(diào)試程序（也要花費(fèi)精力）。,課堂問題,2024/3/17,頻率計(jì)數(shù),頻率計(jì)數(shù)：算法中語(yǔ)句或運(yùn)算的執(zhí)行次數(shù)。 例： x←x+y for i ←1 to n

15、do for i ←1 to n do x ← x + y for j ←1 to n do repeat x ← x +y x=x2

16、 repeat repeat x=x2 (a) (b)

17、 (c) 分析： (a)： x←x+y執(zhí)行了1次 (b)： x←x+y執(zhí)行了n次，x=x2 ，執(zhí)行一次 (c)： x←x+y執(zhí)行了n2次，x=x2 ，執(zhí)行一次 一條語(yǔ)句在整個(gè)程序運(yùn)行時(shí)實(shí)際執(zhí)行時(shí)間=頻率計(jì)數(shù) * 每執(zhí)行一次該語(yǔ)句所需的時(shí)間,2024/3/17,如何克服上述辦法的缺陷？,我們需要的是衡量一個(gè)算法所使用方法、策略的效率的度量，我們要求：a、這個(gè)

18、度量要獨(dú)立于機(jī)器；b、編程語(yǔ)言、程序員，c、我們主要不是關(guān)心小規(guī)模輸入量的情況，而是關(guān)心大輸入量時(shí)的算法運(yùn)行情況。,2024/3/17,正確的解決辦法,因此，我們實(shí)際上只計(jì)算算法中的特定基本操作而省略初始化操作、循環(huán)控制及其他操作。這種基本操作一般同實(shí)際運(yùn)行時(shí)間是成比例的。,2024/3/17,一些基本操作的合理選擇,問題1 在數(shù)組中查找元素x,基本操作選擇：,X與數(shù)組中元素的比較,問題2 矩陣相乘,基本操作選擇：,兩個(gè)實(shí)數(shù)相乘

19、,問題3 排序,基本操作選擇：,兩個(gè)元素的比較,課堂問題,2024/3/17,問題：需要精確計(jì)算運(yùn)算次數(shù)嗎？,解決方法：由于我們只對(duì)大輸入量時(shí)的運(yùn)行情況感興趣且沒必要非常精確地計(jì)算運(yùn)算次數(shù)或運(yùn)算時(shí)間，可以只討論運(yùn)行時(shí)間的增長(zhǎng)率或增長(zhǎng)的階。常見的階有：logn<n<nlogn<n2<n3<2n,我們分析算法的時(shí)間復(fù)雜性時(shí)，我們的主要目的是將此算法同解決同一問題的其他算法或不同的問題的算法相比較，時(shí)間復(fù)雜度是

20、相對(duì)的而不是絕對(duì)的。要精確計(jì)算所有運(yùn)算的次數(shù)，如果不是不可能的話，也是非常麻煩的，實(shí)際上對(duì)于我們的算法分析的實(shí)際目的而言也是不必要的。,2024/3/17,示例 有解決同一問題的兩個(gè)算法A和B，其時(shí)間復(fù)雜度分別為10n2和n3，當(dāng)n比較大時(shí)，系數(shù)10根本不起作用。,2024/3/17,算法C時(shí)間復(fù)雜度為100n2,2024/3/17,,這一點(diǎn)可以從如下數(shù)學(xué)分析結(jié)果看出：,同樣的道理可以用于函數(shù)f(n)=n3+2n2+5n中（假定是算法

21、D的時(shí)間復(fù)雜度）的低階項(xiàng)上。容易看出，隨著n的增大，低階項(xiàng)的影響越來(lái)越小。因此，可以說，算法A、B、C、D的時(shí)間復(fù)雜度分別為n2、n3、n2、n3階的。,2024/3/17,典型的計(jì)算時(shí)間函數(shù)曲線,2024/3/17,,計(jì)算時(shí)間函數(shù)值比較,3,2024/3/17,典型的函數(shù)階,2024/3/17,三個(gè)形式化表達(dá)時(shí)間復(fù)雜性的數(shù)學(xué)符號(hào),,2024/3/17,1）上界函數(shù),定義1 如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有

22、 |f(n)| ≤ c|g(n)| 則記作f(n) = Ο(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于|g(n)|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù)。 f(n)的數(shù)量級(jí)就是g(n)。一般試圖求出最小的g(n)，使得f(n) = Ο(g(n))。,即從n0及以后項(xiàng)，不等式成立。,2024/3/17,定義1.2 如果存在兩個(gè)正常

23、數(shù)c和n0，對(duì)于所有的n≥n0， 有 |f(n)| ≥ c|g(n)| 則記作f(n) = Ω(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是不小于|g(n)|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間f(n)的一個(gè)下界函數(shù)。一般試圖求出“最大”的g(n)，使得f(n) = Ω(g(n))。,2）下界函數(shù),即從n0及以后項(xiàng)，不等式成立。

24、,2024/3/17,定義1.3 如果存在正常數(shù)c1，c2和n0，對(duì)于所有的n≥n0，有 c1|g(n)| ≤|f(n)| ≤ c2|g(n)| 則記作含義：算法在最好和最壞情況下的計(jì)算時(shí)間就一個(gè)常數(shù)因子范圍內(nèi)而言是相同的。可看作： 既有 f(n) = Ω(g(n))，又有f(n) = Ο(g(n)),3）“平均情況”限界函數(shù),為有助于理解，可以認(rèn)為O類似于≤ ； Ω類似于≥ ，而,2024/

25、3/17,例 設(shè)f(n)=10n2+20n,顯然， f(n)=10n2+20n>n2,n>1,所以有f(n)= Ω(n2)。因?yàn)閒(n)=10n2+20n2,所以有f(n)=O(n2)。由以上兩點(diǎn)可以推出,2024/3/17,例 一般地，對(duì)一般多項(xiàng)式f(n)=c1nk+c2n(k-1)+…+ckn+ck+1(c1≠0),f(n)=Ω (nk)。f(n)=O(nk)。由以上兩點(diǎn)可以推出,2024/3/17,最壞情

26、形復(fù)雜度 與 平均情形復(fù)雜度,即使輸入量大小相同，不同的輸入數(shù)據(jù)會(huì)導(dǎo)致基本運(yùn)算執(zhí)行次數(shù)也不同，有時(shí)候還差別很大?？紤]一個(gè)簡(jiǎn)單的問題，即在無(wú)序數(shù)組a[1:n]中查找元素x，我們采用從前向后順序查找法。（假定x必在數(shù)組中）若x在數(shù)組開頭a[1]，則只需一次比較運(yùn)算；若x在數(shù)組末尾a[n]，則要n次比較運(yùn)算；很明顯，同樣的輸入規(guī)模（都有n個(gè)輸入量），但不同情況下要用的運(yùn)算次數(shù)明顯差異很大，上述問題中最壞情形下要用n次比較運(yùn)算。當(dāng)然（這是

27、最壞情形復(fù)雜度），我們可能對(duì)平均情況下的比較次數(shù)更感興趣（這是平均情形復(fù)雜度）。,2024/3/17,最壞情形復(fù)雜度與平均情形復(fù)雜度的形式化定義,符號(hào)的約定 Dn是對(duì)于所考慮問題來(lái)說輸入大小為n的輸入集合；I是Dn的一個(gè)元素，p(I)為I出現(xiàn)的概率，t(I)是算法在輸入I時(shí)所執(zhí)行的基本運(yùn)算次數(shù)。,例如：在無(wú)序數(shù)組中查找查找元素問題中，Dn即表示有n個(gè)元素的所有可能情形。,2024/3/17,算法的平均情形復(fù)雜度,A（n）=∑

28、 p(I) t(I) (I屬于Dn),算法的最壞情形復(fù)雜度,W（n）=max{ t(I)} (I屬于Dn),描述算法的一般情況下的表現(xiàn)，但必須要首先知道輸入數(shù)據(jù)的出現(xiàn)概率，可能要經(jīng)過大規(guī)模的統(tǒng)計(jì)，不一定容易得到，另外，平均情形復(fù)雜度的計(jì)算也可能是個(gè)數(shù)學(xué)難題,描述算法在最壞情況下的表現(xiàn)，相對(duì)容易計(jì)算，在無(wú)法計(jì)算平均情形復(fù)雜度時(shí)，只能計(jì)算最壞情形復(fù)雜度，并以之作為度量算法效率的表準(zhǔn),2024/3/17,例 順序搜索無(wú)序表,輸入E(含n個(gè)元

29、素的序列)n（序列E中元素個(gè)數(shù)）K（搜索元素，設(shè)為整數(shù)，E[i]也設(shè)為整數(shù)）輸出K在序列E中位序，若找不到返回-1,2024/3/17,算法,int seqSearch(int[] E,int n,int K){int ans,index;ans=-1;for(index=0;index<n;index++) if(K==E(index)) { ans=index; break; }

30、return ans;},基本操作：K同E中元素的比較,2024/3/17,最壞情形復(fù)雜度,顯然，當(dāng)K在序列末尾或不在序列中，需要比較n次，所以W（n）=n,2024/3/17,平均情形復(fù)雜度,假定序列中元素互不相同；若K在此序列中，假定K在序列中的位置是等可能的。Ii：代表K在位置i的所有輸入A1(n)= = =,在查找成功的情形下，平均比較次數(shù)約為序列長(zhǎng)度的一半，這同

31、我們的直覺是相符的。,2024/3/17,元素不在序列中的情形,顯然，此時(shí)平均情形復(fù)雜度為A2(n)=n,綜合上述兩種情形（K在序列與不在序列中）,,A(n)=Pr(查找成功時(shí))A1(n)+Pr(查找不成功時(shí))A2(n),設(shè)查找成功的概率為q，而查找不成功的概率顯然為1-q，,2024/3/17,a.q=1(K必在序列中) A(n)=（n+1）/2 b.q=0(K必不在序列中) A(n)= nc.q=1/2(K在序列中概率

32、為一半) A(n)= n3/4+1/4,,2024/3/17,§ 1.3 關(guān)于類c語(yǔ)言與類Pascal語(yǔ)言——SPARKS語(yǔ)言,SPARKS語(yǔ)言類PASCAL語(yǔ)言結(jié)構(gòu)化設(shè)計(jì)經(jīng)常作為教學(xué)用語(yǔ)言,類c語(yǔ)言見教材（此處略）,2024/3/17,1. 基本語(yǔ)法成分,1）數(shù)據(jù)類型 整型 integer 實(shí)型 float 布爾型 boolean 字符型 c

33、har,2）變量聲明 類型說明符 變量； integer i,j; boolean b; char c3）數(shù)組 任意整數(shù)下標(biāo) integer A(1:5,7:20) integer B(5,7:20),2024/3/17,4）賦值運(yùn)算 （變量）←（表達(dá)式） x ← 2 + x;5）邏輯運(yùn)算：and or not6）關(guān)系運(yùn)算：＜

34、 ≤ ＝ ≠ ≥ ＞,2024/3/17,7）控制結(jié)構(gòu)： 順序:（略） 分支: · if condition then S1 else S2 endif · case :cond1:S1;

35、 :cond2:S2; … :condn:Sn :else:Sn+1 endcase,循環(huán): ·while cond do S repeat ·loop S until cond repeat

36、·for vble←start to finish by increment do S repeat,2024/3/17,8) 函數(shù)的定義與調(diào)用 過程定義 procedure NAME((參數(shù)表)) （說明部分） S

37、 end NAME 過程的調(diào)用： CALL 過程名 函數(shù)定義 類型名 procedure NAME((參數(shù)表)) （說明部分） S return (表達(dá)式) end NAME

38、 函數(shù)的引用：x ← function（參數(shù)）；,2024/3/17,9) 變量的分類 a）根據(jù)數(shù)據(jù)類型分類 整型、實(shí)型、字符型等 b）根據(jù)作用域分類： 全程變量、局部變量、形式參數(shù) c）根據(jù)是否帶入、帶出數(shù)據(jù)值/結(jié)果分類： in型變量 out型變量 inout型變量

39、 邊界效應(yīng)：改變了參變量或全程變量的值 函數(shù)：通過函數(shù)值返回輸出結(jié)果，沒有邊界效應(yīng) 純過程：沒有函數(shù)值返回，只通過邊界效應(yīng)帶出輸出結(jié)果,2024/3/17,10) 特殊語(yǔ)句 a）exit 退出當(dāng)前一層的循環(huán) b）return 退出過程 return(表達(dá)式) : 函數(shù)返回

40、結(jié)果 c）goto 無(wú)條件轉(zhuǎn)向語(yǔ)句 goto label 11) 遞歸 a）直接遞歸：過程中包含對(duì)自身的調(diào)用 b）間接遞歸：間接調(diào)用自身12) 輸入輸出 read、print13）注釋 //注釋//,2024/3/17,1.4 基本數(shù)據(jù)結(jié)構(gòu),1. 棧和隊(duì)列線性表： n個(gè)元素的有序表?xiàng)：完?duì)列：特殊的線性表利用動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)——鏈表實(shí)現(xiàn)棧或隊(duì)列利用靜

41、態(tài)數(shù)據(jù)結(jié)構(gòu)——數(shù)組實(shí)現(xiàn)棧或隊(duì)列基于以上兩種表示形式的棧和隊(duì)列上的基本運(yùn)算,2024/3/17,2. 樹 定義1.4 樹（tree）是一個(gè)或多個(gè)結(jié)點(diǎn)的有限集合，它使得：有一個(gè)指定為根（root）的結(jié)點(diǎn)剩余結(jié)點(diǎn)被劃分成m≥0個(gè)不相交的集合： T1，…，Tm 這些集合的每一個(gè)又都是一棵樹，并稱T1，…，Tm為根的子樹。,2024/3/17,關(guān)于樹的重要概念結(jié)點(diǎn)的度（degree）：一個(gè)結(jié)點(diǎn)的子樹數(shù)樹的度

42、：樹中結(jié)點(diǎn)度的最大值結(jié)點(diǎn)的級(jí)（level）（又叫層）：設(shè)根是1級(jí)，若某結(jié)點(diǎn)在p級(jí)，則它的兒子在p+1級(jí)樹的高度（或深度）：樹中結(jié)點(diǎn)的最大級(jí)數(shù)葉子（終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)森林：m≥0個(gè)不相交樹的集合。,2024/3/17,3 二元樹 定義1.5 二元樹（binary tree）是結(jié)點(diǎn)的有限集合，它或者為空，或者由一個(gè)根和兩棵稱為左子樹和右子樹的不相交二元樹所組成。 二元

43、樹與度為2的樹的區(qū)別二元樹性質(zhì)： 引理1.1 一棵二元樹第 i級(jí)的最大結(jié)點(diǎn)數(shù)是2i-1。深度為k的二元樹的最大結(jié)點(diǎn)數(shù)為2k-1,k>0。,2024/3/17,2024/3/17,特殊形態(tài)的二元樹 ① 滿二元樹：深度為k且有2k-1個(gè)結(jié)點(diǎn)的二元樹,,,,,,,,2024/3/17,② 完全二元樹：一棵有n個(gè)結(jié)點(diǎn)深度為k的二元樹，當(dāng)它的 結(jié)點(diǎn)相當(dāng)于深度為k的滿二元樹

44、中編號(hào)為1到 n的結(jié)點(diǎn)時(shí)，稱該二元樹是完全的。 完全二元樹的葉子結(jié)點(diǎn)至多出現(xiàn)在相鄰的兩級(jí)上。 完全二元樹的結(jié)點(diǎn)可以緊湊地存放在一個(gè)一維數(shù)組中（性質(zhì)見引理1.2）。,2024/3/17,③ 堆：堆是一棵完全二元樹，它的每個(gè)結(jié)點(diǎn)的值至少和 該結(jié)點(diǎn)的兒子們（如果存在的話）的值一樣大 （ max-堆）（或小， min-堆）?！、堋《謾z索樹：二分檢索

45、樹Ｔ是一棵二元樹，它或者為空， 或者每個(gè)結(jié)點(diǎn)含有一個(gè)可以比較大小的數(shù)據(jù)元素，且 有：　　　·Ｔ的左子樹的所有元素比根結(jié)點(diǎn)中的元素?。弧　　?#183;Ｔ的右子樹的所有元素比根結(jié)點(diǎn)中的元素大；　　　·Ｔ的左子樹和右子樹也是二分檢索樹?！　∽ⅲ憾謾z索樹要求樹中所有結(jié)點(diǎn)的元素值互異,2024/3/17,3. 圖,圖Ｇ由稱之為結(jié)點(diǎn)Ｖ和邊Ｅ的兩個(gè)集合組成，記為

46、 G=（V，E） 其中，Ｖ是一個(gè)有限非空的結(jié)點(diǎn)集合；Ｅ是結(jié)點(diǎn)對(duì)偶的集合，Ｅ的每一對(duì)偶表示Ｇ的一條邊。,2024/3/17,有關(guān)圖的的重要概念,無(wú)向圖：邊表示為（ｉ，ｊ）有向圖：邊表示為〈ｉ，ｊ〉成本：帶有成本的圖稱為網(wǎng)絡(luò)（帶權(quán)圖）鄰接結(jié)點(diǎn)的度（出度／入度）路徑：由結(jié)點(diǎn)vp到vq的一條路（path）是結(jié)點(diǎn) vp ， vi1 ， vi2 ， … ， vim ， vq的一個(gè)

47、序列，它使得 ( vp ， vi1 ) ，( vi1 ，vi2 ) ， … ，( vim ， vq ) 是E（G）的邊。路的長(zhǎng)度：組成路的邊數(shù)。,2024/3/17,簡(jiǎn)單路徑：除了第一和最后一個(gè)結(jié)點(diǎn)可以相同以外，其它 所有結(jié)點(diǎn)都不同。環(huán)：第一個(gè)和最后一個(gè)結(jié)點(diǎn)相同的簡(jiǎn)單路。連通圖：在無(wú)向圖中，如果每對(duì)結(jié)點(diǎn)之間都存在一條路徑，則

48、 稱該圖是連通的。子圖：是由G的結(jié)點(diǎn)集V的子集（記為VB）和邊集E中連接VB 中結(jié)點(diǎn)的邊的子集所組成的圖。連通分圖：一個(gè)圖的最大連通子圖。有向圖的強(qiáng)連通性：在有向圖中，如果對(duì)于每一對(duì)結(jié)點(diǎn)i和j， 既存在一條從i到j(luò)的路，又存在一條從j

49、 到i的路，則稱該有向圖是強(qiáng)連通的。,2024/3/17,圖的表示方法,鄰接矩陣 鄰接表,2024/3/17,1.5 遞歸和消去遞歸,1. 遞歸 遞歸是一種強(qiáng)有力的設(shè)計(jì)方法 遞歸的效率問題,2024/3/17,例1.3 斐波那契(Fibonacci)序列： F0 = F1 = 1 Fi = Fi-1 +

50、Fi-2 （i>1)算法1.7 求斐波那契數(shù) procedure F(n) //返回第n個(gè)斐波那契數(shù)// integer n if n<= 1 then return(1) else return(F(n-1) + F(n-2)) end if

51、 end F算法效率：對(duì)F(n-1) 、F(n-2)存在大量的重復(fù)計(jì)算改 進(jìn)：保存中間結(jié)果,2024/3/17,例1.4 歐幾里得算法 已知兩個(gè)非負(fù)整數(shù)a和b，且a＞b≥0，求這兩個(gè)數(shù)的最大公因數(shù)。 輾轉(zhuǎn)相除法：若b=0，則a和b的最大公因數(shù)等于a；若b＞0，則a和b的最大公因數(shù)等于b和用b除a的余數(shù)的最大公因數(shù)。算法1.8 求最大公因數(shù) procedure GCD(a,

52、b) // 約定a>b // if b=0 then return(a) else return (GCD(b,a mod b)) endif end GDC 例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;,2024/3/17,例1.5 用遞歸策略設(shè)計(jì)的檢索算法 已

53、知元素x和元素表A（1：n），判斷x是否等于A中某元素的值。 算法1.9 在A（1：n）中檢索x procedure SEARCH(i) //如果在A（1：n）//中有一元素A（k）=x，則將其第一次出現(xiàn)的下標(biāo)k返回，否則返回0// global n,x,A(1:n) case :i>n: return(0) :A(i) =

54、 x; return(i) :else: return(SEARCH(i+1)) endcase end SEARCH,2024/3/17,2. 消去遞歸,直接遞歸的消去規(guī)則： 基本思路：將遞歸調(diào)用的地方用等價(jià)的非遞歸代碼來(lái)代替，并對(duì)return語(yǔ)句做適當(dāng)處理。 13條規(guī)則：處理直接遞歸調(diào)用和return語(yǔ)句，將之轉(zhuǎn)換成等價(jià)的迭代代碼。 初始化 ⑴ 在過程的開

55、始部分，插入說明為棧的代碼并將其初始化為空。在一般情況下，這個(gè)棧用來(lái)存放參數(shù)、局部變量和函數(shù)的值、每次遞歸調(diào)用的返回地址。 ⑵ 將標(biāo)號(hào)L1附于第一條可執(zhí)行語(yǔ)句。然后對(duì)于每一處遞歸調(diào)用都用一組執(zhí)行下列規(guī)則的指令來(lái)代替。,2024/3/17,處理遞歸調(diào)用語(yǔ)句 ⑶ 將所有參數(shù)和局部變量的值存入棧。 棧頂指針可作為一個(gè)全程變量來(lái)看待。 ⑷ 建立第i個(gè)新標(biāo)號(hào)Li，并將i存入棧。這個(gè)標(biāo)號(hào)的i值將用來(lái)計(jì)算返回地址。

56、此標(biāo)號(hào)放在規(guī)則⑺所描述的程序段中。 ⑸ 計(jì)算這次調(diào)用的各實(shí)在參數(shù)（可能是表達(dá)式）的值，并把這些值賦給相應(yīng)的形式參數(shù)。 ⑹ 插入一條無(wú)條件轉(zhuǎn)向語(yǔ)句轉(zhuǎn)向過程的開始部分： goto L1,2024/3/17,對(duì)退出一層遞歸調(diào)用后的處理 ⑺ 如果這過程是函數(shù)，則對(duì)遞歸過程中含有此次函數(shù)調(diào)用的那條語(yǔ)句做如下處理：將該語(yǔ)句的此次函數(shù)調(diào)用部分用從棧頂取回該函數(shù)值的代碼來(lái)代替，其余部分的代碼按原描述方式照抄，并將⑷中建立的

57、標(biāo)號(hào)附于這條語(yǔ)句上。 如果此過程不是函數(shù)，則將⑷中建立的標(biāo)號(hào)附于⑹所產(chǎn)生的轉(zhuǎn)移語(yǔ)句后面的那條語(yǔ)句。 以上步驟消去過程中的遞歸調(diào)用。下面對(duì)過程中出現(xiàn)return語(yǔ)句進(jìn)行處理。 （純過程結(jié)束處的end可看成是一條沒有值與之聯(lián)系的return語(yǔ)句）,2024/3/17,對(duì)每個(gè)有return語(yǔ)句的地方，執(zhí)行下述規(guī)則： ⑻ 如果棧為空，則執(zhí)行正常返回。 ⑼ 否則，將所有輸出參數(shù)（帶有返回值的出口參數(shù)，out/ i

58、nout型）的當(dāng)前值賦給棧頂上的那些對(duì)應(yīng)的變量。 ⑽ 如果棧中有返回地址標(biāo)號(hào)的下標(biāo)，就插入一條此下標(biāo)從棧中退出的代碼，并把這個(gè)下標(biāo)賦給一個(gè)未使用的變量。 ⑾ 從棧中退出所有局部變量和參數(shù)的值并吧它們賦給對(duì)應(yīng)的變量。 ⑿ 如果這個(gè)過程是函數(shù)，則插入以下指令，這些指令用來(lái)計(jì)算緊接在return后面的表達(dá)式并將結(jié)果值存入棧頂。 ⒀ 用返回地址標(biāo)號(hào)的下標(biāo)實(shí)現(xiàn)對(duì)該標(biāo)號(hào)的轉(zhuǎn)向。,2024/3/17,例1.6 遞歸調(diào)用示例

59、 求數(shù)組元素中的最大值算法1.10 求取數(shù)組元素的最大值（遞歸算法） procedure MAX1(i) // 查找數(shù)組A中最大值元素，并返回該元素的最大下標(biāo)。// global integer n,A(1:n),j,k integer i if i A(j) then k←i else k←j

60、endif else k←n endif return(k) //遞歸調(diào)用的返回// end MAX1,2024/3/17,消去上例中的遞歸算法1.11 使用上述的規(guī)則消去例1.10中的遞歸代碼 procedure MAX2(i) local integer j,k; global integer n

61、, A(1:n) integer I integer STACK(1:2*n) top←0 //規(guī)則1，聲明棧的代碼，并初始化為空// L1: if i<n //規(guī)則2，將標(biāo)號(hào)L1賦于第一條可執(zhí)行語(yǔ)句前// then top ←top + 1; STACK(top)←i; // 規(guī)則3，參數(shù)或局

62、 部變量的值入棧// top ←top +1; STACK(top)←2; // 規(guī)則4，建立新 標(biāo)號(hào)2，并入棧/

63、/,2024/3/17,i ←i+1 // 規(guī)則5， 計(jì)算參數(shù)值// goto L1 //規(guī)則6， 無(wú)條件轉(zhuǎn)向算法的開始部分// L2: j ←STACK(top); top ←top-1; // 規(guī)則7， 處理函數(shù)調(diào)用，

64、 并將標(biāo)號(hào)2賦于該語(yǔ)句上// if A(i) > A(j) then k ←I else k ←j endif else k ←n endif,2024/3/17,if top = 0 then return(k) // 規(guī)則8， 如果?？眨瑒t正常返回// else addr ←STACK(top

65、);top ←top-1; // 規(guī)則10， 從 棧中退出返回標(biāo)號(hào)// i ←STACK(top);top ←top-1; // 規(guī)則11， 從棧中退

66、 出局部變量和參數(shù)的值// top ←top+1;STACK(top) ←k; // 規(guī)則12， 計(jì)算返 回值