1、1 一個(gè)問(wèn)題往往有多個(gè)算法一個(gè)問(wèn)題往往有多個(gè)算法 應(yīng)當(dāng)分析算法的品性應(yīng)當(dāng)分析算法的品性怎樣評(píng)價(jià)一個(gè)算法？怎樣評(píng)價(jià)一個(gè)算法？2 一個(gè)算法好不好體現(xiàn)在一個(gè)算法好不好體現(xiàn)在運(yùn)行運(yùn)行該算法所需要的該算法所需要的計(jì)算機(jī)資源計(jì)算機(jī)資源的多少上的多少上所需資源越少，該算法越好；所需資源越少，該算法越好； 計(jì)算機(jī)最重要的資源是計(jì)算機(jī)最重要的資源是時(shí)間和空間時(shí)間和空間 算法分析算法分析對(duì)算法利用這兩種資源的對(duì)算法利用這兩種資源的效率效率做研究做研究 時(shí)間效率：指出正在討論的算法運(yùn)行得有多快；時(shí)間效率：指出正在討論的算法運(yùn)行得有多快； 空間效率：關(guān)心算法需要的額外空間。空間效率：關(guān)心算法需要的額外空間。 研究實(shí)驗(yàn)

2、告訴我們，對(duì)于大多數(shù)問(wèn)題來(lái)說(shuō)，我們?cè)谒俣妊芯繉?shí)驗(yàn)告訴我們，對(duì)于大多數(shù)問(wèn)題來(lái)說(shuō)，我們?cè)谒俣壬夏軌蛉〉玫倪M(jìn)展要遠(yuǎn)大于在空間上的進(jìn)展，上能夠取得的進(jìn)展要遠(yuǎn)大于在空間上的進(jìn)展， 所以我們把主要精力集中在時(shí)間效率上。所以我們把主要精力集中在時(shí)間效率上。3如何評(píng)價(jià)時(shí)間效率？2.1.1 輸入規(guī)模的度量輸入規(guī)模的度量 一個(gè)事實(shí)：?jiǎn)栴}一個(gè)事實(shí)：?jiǎn)栴}規(guī)模規(guī)模越大，算法運(yùn)行時(shí)間越長(zhǎng)。越大，算法運(yùn)行時(shí)間越長(zhǎng)。 將將算法輸入規(guī)模算法輸入規(guī)模n為時(shí)間效率的參數(shù)。為時(shí)間效率的參數(shù)。選擇哪個(gè)（些）參數(shù)作為輸入規(guī)模？選擇哪個(gè)（些）參數(shù)作為輸入規(guī)模？ 42.1.2 運(yùn)行時(shí)間的度量單位運(yùn)行時(shí)間的度量單位 可以采用秒，分，小時(shí)嗎？可

3、以采用秒，分，小時(shí)嗎？ 可以統(tǒng)計(jì)算法每一步的操作次數(shù)嗎？可以統(tǒng)計(jì)算法每一步的操作次數(shù)嗎？一般的做法：一般的做法：把把基本操作基本操作（最重要的操作）次數(shù)（最重要的操作）次數(shù)作為算法運(yùn)作為算法運(yùn)行時(shí)間的度量單位。行時(shí)間的度量單位。思考下面算法的重要操作：思考下面算法的重要操作：排序排序矩陣乘法矩陣乘法5 建立一個(gè)算法時(shí)間效率的分析框架建立一個(gè)算法時(shí)間效率的分析框架 對(duì)于輸入規(guī)模為對(duì)于輸入規(guī)模為n的算法的算法 統(tǒng)計(jì)統(tǒng)計(jì)基本操作執(zhí)行次數(shù)基本操作執(zhí)行次數(shù)C(n)，來(lái)對(duì)其效率進(jìn)行度，來(lái)對(duì)其效率進(jìn)行度量量。 在某個(gè)特定計(jì)算機(jī)上的某個(gè)算法程序的運(yùn)行時(shí)間在某個(gè)特定計(jì)算機(jī)上的某個(gè)算法程序的運(yùn)行時(shí)間 T(n)co

4、pC(n)基本操作的基本操作的執(zhí)行時(shí)間執(zhí)行時(shí)間基本操作次數(shù)基本操作次數(shù)6 對(duì)下面的三個(gè)時(shí)間效率函數(shù)表達(dá)式對(duì)下面的三個(gè)時(shí)間效率函數(shù)表達(dá)式,哪一個(gè)效率哪一個(gè)效率高高? C1(n)=n C2(n)=n3 C3(n)= 10n n=1 1 1 10 n=2 2 8 100 n=3 3 27 1000 n=非常大非常大 結(jié)論：結(jié)論：1 隨隨n的遞增，不同函數(shù)增幅的遞增，不同函數(shù)增幅不同不同2 某些函數(shù)在大規(guī)模時(shí)增幅顯某些函數(shù)在大規(guī)模時(shí)增幅顯著，函數(shù)可以表示增幅的特點(diǎn)著，函數(shù)可以表示增幅的特點(diǎn)3 我們希望選擇大規(guī)模時(shí)，我們希望選擇大規(guī)模時(shí)，時(shí)時(shí)間效率增幅小間效率增幅小的算法的算法7 2.1.3增長(zhǎng)次數(shù)（增

5、長(zhǎng)幅度）增長(zhǎng)次數(shù)（增長(zhǎng)幅度） 特別考慮大規(guī)模的輸入要強(qiáng)調(diào)執(zhí)行次數(shù)的增長(zhǎng)特別考慮大規(guī)模的輸入要強(qiáng)調(diào)執(zhí)行次數(shù)的增長(zhǎng)次數(shù)呢？這是因?yàn)樾∫?guī)模輸入在運(yùn)行時(shí)間上差別次數(shù)呢？這是因?yàn)樾∫?guī)模輸入在運(yùn)行時(shí)間上差別不足以將高效的算法和低效的算法法區(qū)分開(kāi)來(lái)。不足以將高效的算法和低效的算法法區(qū)分開(kāi)來(lái)。8 圖12 各種函數(shù)的曲線9 C(n)可以合理的度量算法的效率，但對(duì)同一個(gè)算可以合理的度量算法的效率，但對(duì)同一個(gè)算法相同的規(guī)模下運(yùn)行時(shí)間就一樣嗎？法相同的規(guī)模下運(yùn)行時(shí)間就一樣嗎？ 考慮順序查找：考慮順序查找： SequentialSearch(A0.n-1,K) /輸入：數(shù)組輸入：數(shù)組A0.n-1,和查找關(guān)鍵字和查找關(guān)鍵

6、字K /輸出：返回第一個(gè)匹配輸出：返回第一個(gè)匹配K的元素下標(biāo)的元素下標(biāo) /如果沒(méi)有匹配的，返回如果沒(méi)有匹配的，返回-1 i=0 While in and AiK do i=i+1 If i0的情況下都的情況下都包含在包含在(n2)中中。162.2.2 符號(hào)符號(hào)定義定義1 把函數(shù)把函數(shù)t(n)包含在包含在O(g(n) 中記作中記作t(n) O(g(n)。稱(chēng)稱(chēng) t(n) 的的階階不高于不高于g (n) 的的階階.成立條件成立條件：對(duì)于：對(duì)于所有所有足夠大足夠大的的n， t(n) 的的上界上界由由g(n)的的常數(shù)倍數(shù)所確定常數(shù)倍數(shù)所確定。即，存在大于。即，存在大于0的的常數(shù)常數(shù)c和非負(fù)的和非負(fù)的整數(shù)

7、整數(shù)n0，使得：對(duì)于所有的，使得：對(duì)于所有的n n0來(lái)說(shuō)，來(lái)說(shuō)， t(n) c g(n)n0之前之前的情況的情況無(wú)關(guān)重?zé)o關(guān)重要要,為為什么？什么？cg(n)t(n)n符號(hào)O：t(n)O(g(n)n0常用函數(shù)符號(hào)：常用函數(shù)符號(hào)： t(n) 一個(gè)算法運(yùn)行的時(shí)間函數(shù)一個(gè)算法運(yùn)行的時(shí)間函數(shù) C(n)基本操作次數(shù)函數(shù)基本操作次數(shù)函數(shù) g(n) 用來(lái)比較的函數(shù)用來(lái)比較的函數(shù)17 t(n)=3n+2。說(shuō)明屬于。說(shuō)明屬于O(n) 當(dāng)當(dāng)nn0=2時(shí)，時(shí)，3n+23n+n4n 此時(shí)此時(shí)c=4, g(n)=n。（向定義式靠攏）（向定義式靠攏） t(n) 4g(n) t(n)O(n)18 t(n)= 6 * 2n+

8、n2 。 可以觀察到對(duì)于可以觀察到對(duì)于nn0=4，有，有n2 2n 所以對(duì)于所以對(duì)于n4，有，有t(n)6 * 2n+ 2n = 7 * 2n g(n)= 2n t(n) 7g(n) t(n) O (2n )。192.2.3 符號(hào)符號(hào)定義定義2 把函數(shù)把函數(shù)t(n)包含在包含在(g(n)中，記作中，記作t(n)(g(n) 。稱(chēng)稱(chēng)t(n)的階不低于的階不低于g(n)的階。的階。成立條件成立條件：對(duì)于：對(duì)于所有足夠大所有足夠大的的n， t(n)的的下界下界由由g(n)的常數(shù)倍所的常數(shù)倍所確定，確定， 即，即，存在大于存在大于0的常數(shù)的常數(shù)c和非負(fù)的整數(shù)和非負(fù)的整數(shù)n0，使得：，使得： 對(duì)于所有的對(duì)

9、于所有的n n0來(lái)說(shuō)，來(lái)說(shuō)， t(n) c g(n)n0之前的情況無(wú)關(guān)重要cg(n)t(n)n符號(hào)：t(n)(g(n)n020存在大于存在大于0的常數(shù)的常數(shù)c和非負(fù)的整數(shù)和非負(fù)的整數(shù)n0，使得：，使得： 對(duì)于所有的對(duì)于所有的n n0來(lái)說(shuō)，來(lái)說(shuō)， t(n) c g(n)對(duì)于所有的對(duì)于所有的n，有，有t(n) = 3n+ 2 3n，因此，因此t(n) (n)。對(duì)于所有的對(duì)于所有的n0，有，有t(n) = 10n2 + 4n+ 2 10n2， 所以所以t(n) (n2)。212.2.4 符號(hào)符號(hào)定義定義 3 把函數(shù)把函數(shù)t(n)包含在包含在(g(n) 中，記作中，記作t(n) (g(n) ;成立條件

10、成立條件：對(duì)于所有足夠大的：對(duì)于所有足夠大的n， t(n) 的的上界和下界上界和下界都由都由g(n)的常數(shù)倍數(shù)所確定，的常數(shù)倍數(shù)所確定，即，存在大于即，存在大于0的常數(shù)的常數(shù)c1，c2和和非負(fù)的整數(shù)和和非負(fù)的整數(shù)n0，使得：，使得： 對(duì)于所有的對(duì)于所有的n n0來(lái)說(shuō)，來(lái)說(shuō)， c2g(n) t(n) c1g(n)n0之前的情況無(wú)關(guān)重要c1 g(n)t(n)n符號(hào)：t(n)(g(n)n0c2 g(n)22 t(n)=n(n-1) 當(dāng)當(dāng)n0時(shí)，時(shí)， n(n-1)=n2-nn2 n(n-1)=n2-n n2-0.5n0.5n(n4)=0.75n2 0.75n2 t(n) n2 t(n) (n2) 23

11、 上面上面3個(gè)符號(hào)稱(chēng)為漸進(jìn)符號(hào)個(gè)符號(hào)稱(chēng)為漸進(jìn)符號(hào) 在問(wèn)題的求解在問(wèn)題的求解規(guī)模充分大規(guī)模充分大的時(shí)候才成立。的時(shí)候才成立。 如，如，N3c的時(shí)候才成立，其中的時(shí)候才成立，其中c是方程是方程N(yùn)32N 的解。當(dāng)?shù)慕狻．?dāng)N c時(shí)，前者反而有時(shí)，前者反而有效。效。242.2.5漸進(jìn)符號(hào)的有用特性漸進(jìn)符號(hào)的有用特性定理定理 如果如果t1(n) O(g1(n) 并且并且t2(n) O(g2(n)， 則則t1(n)+ t2(n)O(maxg1(n), g2(n) (對(duì)于對(duì)于和和符號(hào)，類(lèi)似的斷言也為真符號(hào)，類(lèi)似的斷言也為真) 對(duì)于兩個(gè)對(duì)于兩個(gè)連續(xù)執(zhí)行部分組成的連續(xù)執(zhí)行部分組成的算法，應(yīng)該如算法，應(yīng)該如何應(yīng)用這

12、個(gè)特性呢？何應(yīng)用這個(gè)特性呢？ 它意味著該它意味著該算法的整體效率是由具有較大算法的整體效率是由具有較大的增長(zhǎng)次數(shù)的部分所決定的增長(zhǎng)次數(shù)的部分所決定的，即它的的，即它的效率較效率較差差的部分。的部分。252.2.6 利用極限比較增長(zhǎng)次數(shù)利用極限比較增長(zhǎng)次數(shù) 雖然符號(hào)雖然符號(hào)O， 和和的正式的正式定義定義對(duì)于證明它們的抽對(duì)于證明它們的抽象性質(zhì)是不可缺少的，但我們很少直接用它們來(lái)比象性質(zhì)是不可缺少的，但我們很少直接用它們來(lái)比較兩個(gè)特定函數(shù)的增長(zhǎng)次數(shù)。有一種較為簡(jiǎn)便的比較兩個(gè)特定函數(shù)的增長(zhǎng)次數(shù)。有一種較為簡(jiǎn)便的比較方法，它是基于對(duì)所討論的兩個(gè)函數(shù)的比率求極較方法，它是基于對(duì)所討論的兩個(gè)函數(shù)的比率求極限

13、。有限。有3種極限情況會(huì)發(fā)生：種極限情況會(huì)發(fā)生：大的增長(zhǎng)次數(shù)比表明相同的增長(zhǎng)次數(shù)和表明小的增長(zhǎng)次數(shù)比表明)()()()()()(0)()(limngntngntcngntngntn262.2.7基本的效率類(lèi)型基本的效率類(lèi)型 O(2O(2n n) O(n!)O(n!) O(nO(nn n) )常見(jiàn)的指數(shù)階常見(jiàn)的指數(shù)階O(1)O(1) O(logn)O(logn) O(n)O(n) O(nlogn)O(nlogn)O(nO(n2 2) O(nO(n3 3) ) maxval maxvalAi return maxval第一步：第一步：決定用哪個(gè)決定用哪個(gè)(哪些哪些)參數(shù)作為參數(shù)作為輸入規(guī)模輸入規(guī)模

14、的度量：的度量：數(shù)組元素的個(gè)數(shù)數(shù)組元素的個(gè)數(shù)n31 MaxElement(A0.n-1) /求給定數(shù)組中最大元素的值求給定數(shù)組中最大元素的值 /輸入：實(shí)數(shù)數(shù)組輸入：實(shí)數(shù)數(shù)組A0.n-1 /輸出輸出:A中最大元素的值中最大元素的值 maxvalA0 for i1 to n-1 do if Aimaxval maxvalAi return maxval第二步：第二步：找出算法基本操作：找出算法基本操作：比較？比較？賦值？賦值？32 MaxElement(A0.n-1) /求給定數(shù)組中最大元素的值求給定數(shù)組中最大元素的值 /輸入：實(shí)數(shù)數(shù)組輸入：實(shí)數(shù)數(shù)組A0.n-1 /輸出輸出:A中最大元素的值中最大

15、元素的值 maxvalA0 for i1 to n-1 do if Aimaxval maxvalAi return maxval第三步：第三步：檢查基本操作的執(zhí)行檢查基本操作的執(zhí)行次數(shù)是否只依賴(lài)輸入次數(shù)是否只依賴(lài)輸入規(guī)模：規(guī)模：比較次數(shù)相同比較次數(shù)相同33 MaxElement(A0.n-1) /求給定數(shù)組中最大元素的值求給定數(shù)組中最大元素的值 /輸入：實(shí)數(shù)數(shù)組輸入：實(shí)數(shù)數(shù)組A0.n-1 /輸出輸出:A中最大元素的值中最大元素的值 maxvalA0 for i1 to n-1 do if Aimaxval maxvalAi return maxval第四步：第四步：建立一個(gè)算法建立一個(gè)算法基

16、本操基本操作執(zhí)行次數(shù)的求和表作執(zhí)行次數(shù)的求和表達(dá)式達(dá)式：34把把C(n)記作比較運(yùn)算的執(zhí)行次數(shù)記作比較運(yùn)算的執(zhí)行次數(shù), 由于該算法每執(zhí)行一次循環(huán)就會(huì)做一次比較由于該算法每執(zhí)行一次循環(huán)就會(huì)做一次比較，并且對(duì)于循環(huán)變量并且對(duì)于循環(huán)變量i在在1和和n-1(包含在內(nèi)包含在內(nèi))中的中的每個(gè)值都會(huì)做一次循環(huán)，所以，我們得到每個(gè)值都會(huì)做一次循環(huán)，所以，我們得到C(n)的下列求和表達(dá)式：的下列求和表達(dá)式： 111)(ninC)(11)(11nnnCni35分析非遞歸算法效率的通用方案分析非遞歸算法效率的通用方案1. 決定用哪個(gè)決定用哪個(gè)(哪些哪些)參數(shù)作為輸入?yún)?shù)作為輸入規(guī)模的度量規(guī)模的度量2. 找出算法的找

17、出算法的基本操作基本操作（作為一規(guī)律，它總是（作為一規(guī)律，它總是位于算法的最內(nèi)層循環(huán)中）。位于算法的最內(nèi)層循環(huán)中）。3.檢查基本操作的執(zhí)行次數(shù)檢查基本操作的執(zhí)行次數(shù)是否只依賴(lài)輸入規(guī)是否只依賴(lài)輸入規(guī)模模。如果它還依賴(lài)一些其他的特性，則最差。如果它還依賴(lài)一些其他的特性，則最差效率、平均效率以及最優(yōu)效率（如果必要）效率、平均效率以及最優(yōu)效率（如果必要）需要分別研究。需要分別研究。4.建立一個(gè)算法基本操作執(zhí)行次數(shù)的求和建立一個(gè)算法基本操作執(zhí)行次數(shù)的求和表達(dá)表達(dá)式式。5.利用求和運(yùn)算的標(biāo)公式和法則來(lái)建立一個(gè)操利用求和運(yùn)算的標(biāo)公式和法則來(lái)建立一個(gè)操作次數(shù)的作次數(shù)的閉合公式閉合公式，或者至少確定它的，或者至

18、少確定它的增長(zhǎng)增長(zhǎng)次數(shù)次數(shù)。36例例2 元素惟一性問(wèn)題：驗(yàn)證給定數(shù)組中的元素元素惟一性問(wèn)題：驗(yàn)證給定數(shù)組中的元素是否全部惟一。是否全部惟一。UniqueElements(A0.n-1)/輸入：數(shù)組輸入：數(shù)組A0.n-1/輸出：如果輸出：如果A中的元素全部惟一，返回中的元素全部惟一，返回“true”/ 否則，返回否則，返回“false”. for i0 to n-2 do for ji+1 to n-1 do if Ai=Aj return falseReturn true第一步：第一步：決定用哪個(gè)決定用哪個(gè)(哪些哪些)參數(shù)參數(shù)作為輸入規(guī)模作為輸入規(guī)模的度量：的度量：數(shù)組元素的個(gè)數(shù)數(shù)組元素的個(gè)數(shù)

19、n37 UniqueElements(A0.n-1) for i0 to n-2 do for ji+1 to n-1 do if Ai=Aj return false Return true第二步：第二步：找出算法基本操作：找出算法基本操作：比較比較38 UniqueElements(A0.n-1) for i0 to n-2 do for ji+1 to n-1 do if Ai=Aj return false Return true第三步：第三步：檢查基本操作的執(zhí)行次數(shù)檢查基本操作的執(zhí)行次數(shù)是否只依賴(lài)輸入規(guī)模：是否只依賴(lài)輸入規(guī)模：比較的次數(shù)取決于：比較的次數(shù)取決于：n？相同元素？相同元素

20、？及其位置？及其位置？39最差效率：某個(gè)數(shù)組最差效率：某個(gè)數(shù)組Cworst(n)所做的比較數(shù)所做的比較數(shù)比其它數(shù)組都多。比其它數(shù)組都多。最差情況有哪兩種類(lèi)型？最差情況有哪兩種類(lèi)型？1. 不包括相同元素不包括相同元素2. 最后兩個(gè)元素是唯一一對(duì)相同元素最后兩個(gè)元素是唯一一對(duì)相同元素40 UniqueElements(A0.n-1) for i1 to n-2 do for ji+1 to n-1 do if Ai=Aj return false Return true第四步：第四步：建立一個(gè)算法基本操建立一個(gè)算法基本操作執(zhí)行次數(shù)的作執(zhí)行次數(shù)的求和表求和表達(dá)式達(dá)式：41)(212) 1(2) 1)

21、(2() 1(2) 1)(2(1) 1() 1()1( 1) 1() 1( 1 )(22220202020202011nnnnnnnnnninininnCnininininininijworst這個(gè)結(jié)果是完全可以預(yù)測(cè)的：在最壞的情況下，對(duì)于這個(gè)結(jié)果是完全可以預(yù)測(cè)的：在最壞的情況下，對(duì)于n個(gè)個(gè)元素的所有元素的所有n(n-1)/2對(duì)兩兩組合，該算法都要比較一遍對(duì)兩兩組合，該算法都要比較一遍。總共有總共有0到到n-2個(gè)元素個(gè)元素需要考察需要考察內(nèi)循環(huán)的一次操作內(nèi)循環(huán)的一次操作對(duì)于給定的對(duì)于給定的i內(nèi)循環(huán)從內(nèi)循環(huán)從i+1到到n-1進(jìn)行比較進(jìn)行比較42 例例3 給定給定n階方陣階方陣A和和B計(jì)算乘積計(jì)算

22、乘積C=AB MatrixMul(A0.n-1,0.n-1, B0 .n-1,0.n-1) For i=0 to n-1 do for j=0 to n-1 do Ci,j=0.0 for k=0 to n-1 do Ci,j=Ci,j+Ai,k*Bk,j Return C11111123111111( )1=nnnnnniiiiiiC nnnn 43 前面前面3道例題，似乎很簡(jiǎn)單道例題，似乎很簡(jiǎn)單 但在某些時(shí)候會(huì)有困難：但在某些時(shí)候會(huì)有困難： 循環(huán)變量無(wú)規(guī)律變化，過(guò)于復(fù)雜而無(wú)法求解的求循環(huán)變量無(wú)規(guī)律變化，過(guò)于復(fù)雜而無(wú)法求解的求和表達(dá)式，分析平均情況的難度等。和表達(dá)式，分析平均情況的難度等。4

23、4例例4 求一個(gè)十進(jìn)制正整數(shù)在二進(jìn)制表示中的二進(jìn)制求一個(gè)十進(jìn)制正整數(shù)在二進(jìn)制表示中的二進(jìn)制數(shù)字個(gè)數(shù)數(shù)字個(gè)數(shù)Binary(n)/輸入正整數(shù)輸入正整數(shù)nCount=1While n1 do count=count+1 n=Return count2/n 基本運(yùn)算的選擇？基本運(yùn)算的選擇？ 比較運(yùn)算比較運(yùn)算 OR 循環(huán)體中運(yùn)算？循環(huán)體中運(yùn)算？ 循環(huán)次數(shù)？循環(huán)次數(shù)？ 每次循環(huán)，每次循環(huán)，n基本減半，循環(huán)次數(shù)大概為基本減半，循環(huán)次數(shù)大概為2log1n 452.4 遞歸算法遞歸算法的數(shù)學(xué)分析的數(shù)學(xué)分析例例1 對(duì)于任意非負(fù)整數(shù)對(duì)于任意非負(fù)整數(shù)n,計(jì)算階乘函數(shù)計(jì)算階乘函數(shù)F(n)=n!的值。的值。 當(dāng)當(dāng)n1時(shí)，

24、時(shí)，F(xiàn)(n)=F(n-1)n，且，且0!=1算法算法 F(n) /輸入：非負(fù)整數(shù)輸入：非負(fù)整數(shù)n if n=0 return 1 else return F(n-1)*n用用n本身來(lái)指出算法的輸入規(guī)模本身來(lái)指出算法的輸入規(guī)模該該算法的基本操作是乘法算法的基本操作是乘法，它的執(zhí)行次數(shù)記作，它的執(zhí)行次數(shù)記作M(n)，思考應(yīng)該如何構(gòu)造表達(dá)式思考應(yīng)該如何構(gòu)造表達(dá)式?46用到的乘法數(shù)量用到的乘法數(shù)量M(n)需要滿(mǎn)足這個(gè)等式：需要滿(mǎn)足這個(gè)等式： 當(dāng)當(dāng)n0時(shí)，時(shí)，M(n)= M(n-1)+ 1if n=0 return 1 else return F(n-1)*n規(guī)模為規(guī)模為n的階乘的乘法數(shù)量的階乘的乘法數(shù)

25、量做一次乘法做一次乘法F(n-1)*n做完一次乘法后，階乘規(guī)做完一次乘法后，階乘規(guī)模變?yōu)槟Ｗ優(yōu)閚-147M(n)=M(n-1)+1 =M(n-2)+1+1 =M(n-3)+1+1+1 =M(n-i)+i =M(n-n)+n =M(0)+n =n初始條件初始條件M(0)=0if n=0 return 1 else return F(n-1)*n48分析遞歸算法效率的通用方案分析遞歸算法效率的通用方案1.決定用哪個(gè)（哪些）參數(shù)作為決定用哪個(gè)（哪些）參數(shù)作為輸入規(guī)模的度量輸入規(guī)模的度量。2.找出找出算法的基本操作算法的基本操作。3.檢查一下，對(duì)于相同規(guī)模的不同輸入，基本操作檢查一下，對(duì)于相同規(guī)模的不

26、同輸入，基本操作的的執(zhí)行次數(shù)是否不同執(zhí)行次數(shù)是否不同。如果不同，則必須對(duì)最差。如果不同，則必須對(duì)最差效率、平均效率以及最優(yōu)效率作單獨(dú)研究。效率、平均效率以及最優(yōu)效率作單獨(dú)研究。4.對(duì)于算法基本操作的執(zhí)行次數(shù)，建立一個(gè)對(duì)于算法基本操作的執(zhí)行次數(shù)，建立一個(gè)遞推關(guān)遞推關(guān)系系以及以及相應(yīng)的初始條件相應(yīng)的初始條件。5.解這個(gè)遞推式解這個(gè)遞推式，或者至少確定它有解的增長(zhǎng)次數(shù)。，或者至少確定它有解的增長(zhǎng)次數(shù)。49例例2 漢諾塔問(wèn)題漢諾塔問(wèn)題. 三根柱子三根柱子A,B,C, 在在A上有上有n個(gè)半個(gè)半徑不同的中間有孔的圓盤(pán)徑不同的中間有孔的圓盤(pán), 從下而上半徑遞減從下而上半徑遞減. 按照下述規(guī)則將所有盤(pán)子從源盤(pán)

27、按照下述規(guī)則將所有盤(pán)子從源盤(pán)A搬到目的搬到目的C, 將將B做輔助過(guò)渡做輔助過(guò)渡:一次只能搬動(dòng)一個(gè)盤(pán)子一次只能搬動(dòng)一個(gè)盤(pán)子任何時(shí)候大盤(pán)子不能在小盤(pán)子上面任何時(shí)候大盤(pán)子不能在小盤(pán)子上面50解決思路：解決思路：n=1時(shí)時(shí), 搬動(dòng)一個(gè)盤(pán)子即可搬動(dòng)一個(gè)盤(pán)子即可;n1時(shí)時(shí), 分三步執(zhí)行分三步執(zhí)行. (1)將將n1個(gè)盤(pán)子個(gè)盤(pán)子(最大的最大的 除外除外)從源移至輔助柱從源移至輔助柱; (2)將最大盤(pán)從源移至目的將最大盤(pán)從源移至目的; (3)將在輔助柱上的將在輔助柱上的n1 個(gè)盤(pán)子移至目的柱個(gè)盤(pán)子移至目的柱. 問(wèn)題規(guī)模問(wèn)題規(guī)模是什么？是什么？ 基本操作基本操作是什么？是什么？ 時(shí)間效率時(shí)間效率表達(dá)式？表達(dá)式？5

28、1 分析：分析： 1. 算法可以直接給出的解答是當(dāng)算法可以直接給出的解答是當(dāng)n=1時(shí)，需要一個(gè)單位時(shí)，需要一個(gè)單位時(shí)間的工作量時(shí)間的工作量,M(1)=1 2. 第一步和第三步都是將第一步和第三步都是將n1個(gè)盤(pán)子從一個(gè)柱移到另一個(gè)盤(pán)子從一個(gè)柱移到另一個(gè)，所以移個(gè)，所以移n個(gè)盤(pán)子的問(wèn)題可以分成個(gè)盤(pán)子的問(wèn)題可以分成2個(gè)移個(gè)移n1個(gè)盤(pán)子的個(gè)盤(pán)子的問(wèn)題。問(wèn)題。 3. 其余的工作量：第二步需要一個(gè)單位時(shí)間的工作量。其余的工作量：第二步需要一個(gè)單位時(shí)間的工作量。 M(1) = 1,(n =1) M(n)= 2 M(n-1) +1, (n1)52 M(n)=2 M(n-1) +1 =2(2M(n-2)+1)+

29、1 =22M(n-2)+2+1 =22(2M(n-3)+1)+2+1 =23M(n-3)+22+2+1 = 2iM(n-i)+2i-1+2+1 = 2n-1M(1)+2n-2+2+1 = 2n-1+2n-2+2+1=2n-153 前面的例子：前面的例子： 求一個(gè)十求一個(gè)十進(jìn)制正整數(shù)在二進(jìn)制表示進(jìn)制正整數(shù)在二進(jìn)制表示中的二進(jìn)制數(shù)字個(gè)數(shù)中的二進(jìn)制數(shù)字個(gè)數(shù) Binary(n) /輸入正整數(shù)輸入正整數(shù)n Count=1 While n1 do count=count+1 n= Return count2/ n遞歸版本BinRec(n)If n=1 return 1Else return BinRec(

30、 )+12/ n54 目的：目的： 1 說(shuō)明計(jì)算斐波那契數(shù)的算法以及效率分析說(shuō)明計(jì)算斐波那契數(shù)的算法以及效率分析 2 說(shuō)明算法分析中遞推關(guān)系的一些求解方法說(shuō)明算法分析中遞推關(guān)系的一些求解方法 （P357 附錄附錄B）55斐波那契數(shù)列斐波那契數(shù)列0,1,1,2,3,5,8,13,21,34,觀察特點(diǎn)是什么？觀察特點(diǎn)是什么？從第從第3個(gè)數(shù)開(kāi)始每一個(gè)數(shù)是前兩個(gè)數(shù)之和。個(gè)數(shù)開(kāi)始每一個(gè)數(shù)是前兩個(gè)數(shù)之和。如何寫(xiě)成遞推式？：如何寫(xiě)成遞推式？： 當(dāng)當(dāng)n1時(shí)，時(shí)，F(xiàn)(n)=F(n-1)+F(n-2) F(0)=0,F(1)=1注意：注意：后面問(wèn)題的后面問(wèn)題的n均從均從0開(kāi)始。開(kāi)始。56算法算法1 F(n)/根據(jù)

31、定義，遞歸計(jì)算第根據(jù)定義，遞歸計(jì)算第n個(gè)斐波那契數(shù)個(gè)斐波那契數(shù)/輸入：一個(gè)非負(fù)整數(shù)輸入：一個(gè)非負(fù)整數(shù)n/輸出：第輸出：第n個(gè)斐波那契數(shù)個(gè)斐波那契數(shù) if n1 return n else return F(n-1)+F(n-2)用什么做問(wèn)題規(guī)模？用什么做問(wèn)題規(guī)模？基本操作？基本操作？是否有其他因素影響基本操作次數(shù)？是否有其他因素影響基本操作次數(shù)？寫(xiě)成遞推式。寫(xiě)成遞推式。57 if n1 return n else return F(n-1)+F(n-2)當(dāng)當(dāng)n1時(shí)，時(shí)，A(n)=A(n-1)+A(n-2)+1; A(0)=0 ; A(1)=0 58當(dāng)當(dāng)n1時(shí)，時(shí)，A(n)=A(n-1)+A(n

32、-2)+1 對(duì)該遞歸式的分析對(duì)該遞歸式的分析 1 采用估計(jì)的方式采用估計(jì)的方式 2 采用精確計(jì)算方式采用精確計(jì)算方式(后面說(shuō)明后面說(shuō)明)F(4)F(5)F(3)F(3)F(2)F(2)F(1)F(1)F(2)F(1)F(0)F(1)F(0)F(1)F(0)n=5時(shí)，計(jì)算斐波那契數(shù)的遞歸調(diào)用樹(shù)59改進(jìn)思想：改進(jìn)思想：通過(guò)簡(jiǎn)單地對(duì)斐波那契數(shù)列的連續(xù)元素進(jìn)行迭代計(jì)算通過(guò)簡(jiǎn)單地對(duì)斐波那契數(shù)列的連續(xù)元素進(jìn)行迭代計(jì)算算法算法2 Fib(n)/根據(jù)定義，迭代計(jì)算第根據(jù)定義，迭代計(jì)算第n個(gè)斐波那契數(shù)個(gè)斐波那契數(shù)/輸入：一個(gè)非負(fù)整數(shù)輸入：一個(gè)非負(fù)整數(shù)n/輸出：第輸出：第n個(gè)斐波那契數(shù)個(gè)斐波那契數(shù) F00;F11

33、 for i2 to n do FiFi-1+Fi-2 return F(n)基本操作次數(shù)是多少？基本操作次數(shù)是多少？ 算法要做算法要做n-1次加法運(yùn)算。次加法運(yùn)算。空間效率分析：空間效率分析： 沒(méi)有必要特意使用一個(gè)數(shù)組在存儲(chǔ)沒(méi)有必要特意使用一個(gè)數(shù)組在存儲(chǔ)斐波那契數(shù)列的前面元素：為斐波那契數(shù)列的前面元素：為了完成該任務(wù)，了完成該任務(wù)，只需要存儲(chǔ)兩個(gè)元素只需要存儲(chǔ)兩個(gè)元素就足夠了。就足夠了。60 算法算法3 效率類(lèi)型為效率類(lèi)型為(logn) 基于等式基于等式 例：例：211111101110)3()2()2() 1 ( 時(shí)，2n當(dāng)FFFF3221111021111110)4() 3() 3()2( 時(shí)，3n當(dāng)3FFFFnnFnFnFnF1110) 1()()() 1( 時(shí)，1n當(dāng)61 P358 附錄附錄B 1. 前向替代法前向替代法 x(n)=2x(n-1)+1，且，且x(1)=1 前幾項(xiàng)：前幾項(xiàng)：x(1)=1 x(2)=3 x(3)=7 x(4)=15 找規(guī)律：找規(guī)律：x(n)=2n-1 然后，數(shù)學(xué)歸納法證明。然后，數(shù)學(xué)歸納法證明。62 2 反向替代法反向替代法M(n)=M(n-1)+1 =M(n-2)+1+1 =M(n-3)+1+1+1 =M(n-i)+i =M(n-n)+n =M(0)+n =n63