第2章算法效率分析基礎(chǔ)ppt課件

1、1第2章 算法效率分析根底一個(gè)問題往往有多個(gè)算法，該當(dāng)分析算法的品性怎樣評(píng)價(jià)一個(gè)算法？涉及的概念：?jiǎn)栴}的規(guī)模大小、根本操作、計(jì)算復(fù)雜度、復(fù)雜度的量級(jí)、上下界掌握循壞算法與遞歸算法的復(fù)雜度分析方法2正確性任務(wù)量空間用量簡(jiǎn)單性最優(yōu)型34順序查找：SequentialSearch(A0.n-1, x) /輸入：數(shù)組A0.n-1,和查找關(guān)鍵字x /輸出：前往第一個(gè)匹配x 的元素下標(biāo) /假設(shè)沒有匹配的，前往-1i=0;while in and Ai x do i=i+1;If in then return i else return -1;什么是根本運(yùn)算什么是最壞情況什么是最好情況在表A中查找關(guān)鍵字x5

2、6782.1 分析框架如何評(píng)價(jià)時(shí)間效率？2.1.1 輸入規(guī)模的度量 一個(gè)現(xiàn)實(shí)：?jiǎn)栴}規(guī)模越大，算法運(yùn)轉(zhuǎn)時(shí)間越長(zhǎng)。 將算法輸入規(guī)模n為時(shí)間效率的參數(shù)。選擇哪個(gè)些參數(shù)作為輸入規(guī)模？ 9一個(gè)算法好不好表達(dá)在運(yùn)轉(zhuǎn)該算法所需求的計(jì)算機(jī)資源的多少上所需資源越少，該算法越好；計(jì)算機(jī)最重要的資源是時(shí)間和空間 算法分析對(duì)算法利用這兩種資源的效率做研討時(shí)間效率：指出正在討論的算法運(yùn)轉(zhuǎn)得有多快；空間效率：關(guān)懷算法需求的額外空間。研討實(shí)驗(yàn)通知我們，對(duì)于大多數(shù)問題來說，我們?cè)谒俣壬峡梢垣@得的進(jìn)展要遠(yuǎn)大于在空間上的進(jìn)展，所以我們把主要精神集中在時(shí)間效率上。102.1.2 運(yùn)轉(zhuǎn)時(shí)間的度量單位 可以采用秒，分，小時(shí)嗎？ 可以統(tǒng)

3、計(jì)算法每一步的操作次數(shù)嗎？普通的做法：把根本操作最重要的操作次數(shù)作為算法運(yùn)轉(zhuǎn)時(shí)間的度量單位。思索下面算法的重要操作：排序矩陣乘法11建立一個(gè)算法時(shí)間效率的分析框架對(duì)于輸入規(guī)模為n的算法統(tǒng)計(jì)根本操作執(zhí)行次數(shù)C(n)，來對(duì)其效率進(jìn)展度量。在某個(gè)特定計(jì)算機(jī)上的某個(gè)算法程序的運(yùn)轉(zhuǎn)時(shí)間T(n)copC(n)根本操作的執(zhí)行時(shí)間根本操作次數(shù)12對(duì)下面的三個(gè)時(shí)間效率函數(shù)表達(dá)式, 哪一個(gè)效率高?C1(n)=nC2(n)=n3C3(n)= 10nn=1 1 1 10n=2 2 8 100 n=3 3 27 1000n=非常大 結(jié)論：1 隨n的遞增，不同函數(shù)增幅不同2 某些函數(shù)在大規(guī)模時(shí)增幅顯著，函數(shù)可以表示增幅的

4、特點(diǎn)3 我們希望選擇大規(guī)模時(shí)，時(shí)間效率增幅小的算法132.1.3增長(zhǎng)次數(shù)增長(zhǎng)幅度 特別思索大規(guī)模的輸入要強(qiáng)調(diào)執(zhí)行次數(shù)的增長(zhǎng)次數(shù)呢？這是由于小規(guī)模輸入在運(yùn)轉(zhuǎn)時(shí)間上差別缺乏以將高效的算法和低效的算法法區(qū)分開來。14 圖12 各種函數(shù)的曲線152.1.4 算法的最優(yōu)、最差和平均效率一個(gè)算法的最差效率是指當(dāng)輸入規(guī)模為n時(shí)，算法的最壞情況下的效率。這時(shí)，相對(duì)于其他規(guī)模為n的輸入，該算法的運(yùn)轉(zhuǎn)時(shí)間最長(zhǎng)。為什么要思索最壞效率？提供了對(duì)任何規(guī)模為n的實(shí)例，算法運(yùn)轉(zhuǎn)的上界Cworst(n) 16 一個(gè)算法的最優(yōu)效率是指當(dāng)輸入規(guī)模為n時(shí)，算法在最優(yōu)情況下的效率。這時(shí)，與其它規(guī)模為n的輸入相比，該算法運(yùn)轉(zhuǎn)得最快。

5、然而，無論是最差效率分析還是最優(yōu)效率分析都不能提供一種必要的信息：在“典型或者“隨機(jī)輸入的情況下， 一個(gè)算法會(huì)具有什么樣的行為。這正是平均效率試圖提供應(yīng)我們信息。 17算法計(jì)算復(fù)雜度的定義182.1.5 分析框架概要算法的時(shí)間效率和空間效率都用輸入規(guī)模的函數(shù)進(jìn)展度量。我們用算法根本操作的執(zhí)行次數(shù)來度量算時(shí)間效率。經(jīng)過計(jì)算算法耗費(fèi)的額外存儲(chǔ)單元的數(shù)量來度量空間效率。在輸入規(guī)模一樣的情況下，有些算法的效率會(huì)的顯著差別。對(duì)于這樣的算法，我們需求區(qū)分最差效率，平均效率和最優(yōu)效率。本框架主要關(guān)懷，當(dāng)算法的輸入規(guī)模趨向于無限大的時(shí)候，其運(yùn)轉(zhuǎn)時(shí)間耗費(fèi)的額外空間函數(shù)的增長(zhǎng)次數(shù)。19復(fù)雜度函數(shù)的階2.2 漸進(jìn)符

6、號(hào)和根本效率類型2021例題2223留意上面3個(gè)符號(hào) O， 稱為漸進(jìn)符號(hào)在問題的求解規(guī)模充分大的時(shí)候才成立。如，N3c的時(shí)候才成立，其中c是方程N(yùn)32N 的解。當(dāng)N c時(shí)，前者反而有效。242.2.5漸進(jìn)符號(hào)的有用特性定理 假設(shè)t1(n) O(g1(n) 并且t2(n) O(g2(n)， 那么t1(n)+ t2(n)O(maxg1(n), g2(n) (對(duì)于和符號(hào)，類似的斷言也為真) 對(duì)于兩個(gè)延續(xù)執(zhí)行部分組成的算法，應(yīng)該如何運(yùn)用這個(gè)特性呢？它意味著該算法的整體效率是由具有較大的增長(zhǎng)次數(shù)的部分所決議的，即它的效率較差的部分.252.2.6 利用極限比較增長(zhǎng)次數(shù) 雖然符號(hào)O， 和的正式定義對(duì)于證明

7、它們的籠統(tǒng)性質(zhì)是不可短少的，但我們很少直接用它們來比較兩個(gè)特定函數(shù)的增長(zhǎng)次數(shù)。有一種較為簡(jiǎn)便的比較方法，它是基于對(duì)所計(jì)論的兩個(gè)函數(shù)的比率求極限。有3種極限情況會(huì)發(fā)生：262.2.7根本的效率類型 O(2n)O(n!)O(nn)常見的指數(shù)階O(1)O(logn)O(n)O(nlogn)O(n2)O(n3) maxval maxvalAi; return maxval;第一步：決議用哪個(gè)(哪些)參數(shù)作為輸入規(guī)模的度量：數(shù)組元素的個(gè)數(shù)n31MaxElement(A0.n-1) /求給定數(shù)組中最大元素的值 /輸入：實(shí)數(shù)數(shù)組A0.n-1 /輸出:A中最大元素的值 maxvalA0； for i1 to

8、n-1 do if Aimaxval maxvalAi； return maxval第二步：找出算法根本操作：比較？賦值？32第三步：檢查根本操作的執(zhí)行次數(shù)能否只依賴輸入規(guī)模：比較次數(shù)一樣MaxElement(A0.n-1) /求給定數(shù)組中最大元素的值 /輸入：實(shí)數(shù)數(shù)組A0.n-1 /輸出:A中最大元素的值 maxvalA0； for i1 to n-1 do if Aimaxval maxvalAi； return maxval33第四步：建立一個(gè)算法根本操作執(zhí)行次數(shù)的求和表達(dá)式：MaxElement(A0.n-1) /求給定數(shù)組中最大元素的值 /輸入：實(shí)數(shù)數(shù)組A0.n-1 /輸出:A中最大

9、元素的值 maxvalA0； for i1 to n-1 do if Aimaxval maxvalAi； return maxval34把C(n)記作比較運(yùn)算的執(zhí)行次數(shù), 由于該算法每執(zhí)行一次循環(huán)就會(huì)做一次比較，并且對(duì)于循環(huán)變量i在1和n-1(包含在內(nèi))中的每個(gè)值都會(huì)做一次循環(huán)，所以，我們得到C(n)的以下求和表達(dá)式： 35算法最優(yōu)性36分析非遞歸算法效率的通用方案1. 決議用哪個(gè)(哪些)參數(shù)作為輸入規(guī)模的度量2. 找出算法的根本操作作為一規(guī)律，它總是位于算法的最內(nèi)層循環(huán)中。檢查根本操作的執(zhí)行次數(shù)能否只依賴輸入規(guī)模。假設(shè)它還依賴一些其他的特性，那么最差效率、平均效率以及最優(yōu)效率假設(shè)必要需求分

10、別研討。建立一個(gè)算法根本操作執(zhí)行次數(shù)的求和表達(dá)式。利用求和運(yùn)算的標(biāo)公式和法那么來建立一個(gè)操作次數(shù)的閉合公式，或者至少確定它的增長(zhǎng)次數(shù)。37例2 元素獨(dú)一性問題：驗(yàn)證給定數(shù)組中的元素能否全部獨(dú)一互不相等。UniqueElements(A0.n-1)/輸入：數(shù)組A0.n-1/輸出：假設(shè)A中的元素全部獨(dú)一，前往“true/ 否那么，前往“false. for i0 to n-2 do for ji+1 to n-1 do if Ai=Aj return falseReturn true第一步：決議用哪個(gè)(哪些)參數(shù)作為輸入規(guī)模的度量：數(shù)組元素的個(gè)數(shù)n38UniqueElements(A0.n-1)f

11、or i0 to n-2 do for ji+1 to n-1 do if Ai=Aj return falseReturn true第二步：找出算法根本操作：比較39UniqueElements(A0.n-1)for i0 to n-2 do for ji+1 to n-1 do if Ai=Aj return falseReturn true第三步：檢查根本操作的執(zhí)行次數(shù)能否只依賴輸入規(guī)模：比較的次數(shù)取決于：n？一樣元素？及其位置？40最差效率：某個(gè)數(shù)組Cworst(n)所做的比較數(shù)比其它數(shù)組都多。有哪兩種類型？不包括一樣元素最后兩個(gè)元素是獨(dú)一一對(duì)一樣元素41UniqueElements(

12、A0.n-1)for i1 to n-2 do for ji+1 to n-1 do if Ai=Aj return falseReturn true第四步：建立一個(gè)算法根本操作執(zhí)行次數(shù)的求和表達(dá)式：42這個(gè)結(jié)果是完全可以預(yù)測(cè)的：在最壞的情況下，對(duì)于n個(gè)元素的一切n(n-1)/2對(duì)兩兩組合，該算法都要比較一遍?？偣灿?到n-2個(gè)元素需求調(diào)查內(nèi)循環(huán)的一次操作對(duì)于給定的i內(nèi)循環(huán)從i+1到n-1進(jìn)展比較43例3 給定n階方陣A和B計(jì)算乘積C=ABAlgorithm 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

13、-1 do Ci,j=0.0; for k=0 to n-1 do Ci,j=Ci,j+Ai,k*Bk,j； end of for end of forend of forReturn C44前面3道例題，似乎很簡(jiǎn)單但在某些時(shí)候會(huì)有困難：循環(huán)變量無規(guī)律變化，過于復(fù)雜而無法求解的求和表達(dá)式，分析平均情況的難度等。45例4 設(shè)計(jì)算法求一個(gè)十進(jìn)制正整數(shù)在二進(jìn)制表示中的二進(jìn)制數(shù)字個(gè)數(shù)， 并分析算法的計(jì)算復(fù)雜度算法思想Binary(n)/輸入十進(jìn)制正整數(shù)n count :=1 While n1 do count := count+1 n :=Return count給定f(x)的值， 求n462.4 遞

14、歸算法的復(fù)雜度分析例1 對(duì)于恣意非負(fù)整數(shù)n,計(jì)算階乘函數(shù)F(n)=n!的值。 當(dāng)n1時(shí)，F(xiàn)(n)=F(n-1)n 且0!=1算法 F(n) /輸入：非負(fù)整數(shù)n if n=0 return 1 else return F(n-1)*n用n本身來指出算法的輸入規(guī)模該算法的根本操作是乘法，它的執(zhí)行次數(shù)記作M(n)，思索應(yīng)該如何構(gòu)造表達(dá)式?47用到的乘法數(shù)量M(n)需求滿足這個(gè)等式： 當(dāng)n0時(shí)，M(n)= M(n-1)+ 1if n=0 return 1 else return F(n-1)*n 規(guī)模為n的階乘的乘法數(shù)量做一次乘法F(n-1)*n做完一次乘法后，階乘規(guī)模變?yōu)閚-148M(n)=M(n-

15、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)*n49分析遞歸算法效率的通用方案決議用哪個(gè)哪些參數(shù)作為輸入規(guī)模的度量。找出算法的根本操作。檢查一下，對(duì)于一樣規(guī)模的不同輸入，根本操作的執(zhí)行次數(shù)能否不同。假設(shè)不同，那么必需對(duì)最差效率、平均效率以及最優(yōu)效率作單獨(dú)研討。對(duì)于算法根本操作的執(zhí)行次數(shù)，建立一個(gè)遞推關(guān)系以及相應(yīng)的初始條件。解這個(gè)遞推式，或者至少確定它有解的增長(zhǎng)次數(shù)。50例2 漢諾塔問題. 三根柱子A,B,C, 在A上有n個(gè)半徑不同

16、的中間有孔的圓盤, 從下而上半徑遞減. 按照下述規(guī)那么將一切盤子從源盤A搬到目的C, 將B做輔助過渡:一次只能搬動(dòng)一個(gè)盤子任何時(shí)候大盤子不能在小盤子上面51處理思緒n=1時(shí), 搬動(dòng)一個(gè)盤子即可;n1時(shí), 分三步執(zhí)行. (1)將n1個(gè)盤子(最大的除外)從源移至輔助柱;(2)將最大盤從源移至目的;(3)將在輔助柱上的n1個(gè)盤子移至目的柱.問題規(guī)模是什么？根本操作是什么？時(shí)間效率表達(dá)式？52分析：1、算法可以直接給出的解答是當(dāng)n=1時(shí)，需求一個(gè)單位時(shí)間的任務(wù)量,M(1)=12、 第一步和第三步都是將n1個(gè)盤子從一個(gè)柱移到另一個(gè)，所以移n個(gè)盤子的問題可以分成2個(gè)移n1個(gè)盤子的問題。3 、其他的任務(wù)量：

17、第二步需求一個(gè)單位時(shí)間的任務(wù)量。M(1) = 1,(n =1)M(n)= 2 M(n-1) +1, (n1)53M(n)=2 M(n-1) +1 =2(2M(n-2)+1)+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-154前面的例子： 求一個(gè)十進(jìn)制正整數(shù)在二進(jìn)制表示中的二進(jìn)制數(shù)字個(gè)數(shù)Binary(n)/輸入正整數(shù)nCount=1While n1 do count=count+1 n=Return count遞歸版本B

18、inRec(n)If n=1 return 1Else return BinRec( )+1552.5 例題：斐波那契數(shù)列目的：1、 闡明計(jì)算斐波那契數(shù)的算法以及效率分析2、 闡明算法分析中遞推關(guān)系的一些求解方法 P357 附錄B56斐波那契數(shù)列0,1,1,2,3,5,8,13,21,34,察看特點(diǎn)是什么？從第3個(gè)數(shù)開場(chǎng)每一個(gè)數(shù)是前兩個(gè)數(shù)之和。如何寫成遞推式？： 當(dāng)n1時(shí)，F(xiàn)(n)=F(n-1)+F(n-2) F(0)=0,F(1)=1留意：后面問題的n均從0開場(chǎng)。57算法1 F(n)/根據(jù)定義，遞歸計(jì)算第n個(gè)斐波那契數(shù)/輸入：一個(gè)非負(fù)整數(shù)n/輸出：第n個(gè)斐波那契數(shù) if n1 return

19、n else return F(n-1)+F(n-2)用什么做問題規(guī)模？根本操作？能否有其他要素影響根本操作次數(shù)？寫成遞推式。58 if n1 return n else return F(n-1)+F(n-2)當(dāng)n1時(shí)，A(n)=A(n-1)+A(n-2)+1A(0)=0 , A(1)=0 59當(dāng)n1時(shí)，A(n)=A(n-1)+A(n-2)+1對(duì)該遞歸式的分析1 采用估計(jì)的方式2 采用準(zhǔn)確計(jì)算方式(后面闡明)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)用樹效率不高的緣由:反復(fù)計(jì)算一樣的

20、函數(shù)值.60改良思想：經(jīng)過簡(jiǎn)單地對(duì)斐波那契數(shù)列的延續(xù)元素進(jìn)展迭代計(jì)算算法2 Fib(n)/根據(jù)定義，迭代計(jì)算第n個(gè)斐波那契數(shù)/輸入：一個(gè)非負(fù)整數(shù)n/輸出：第n個(gè)斐波那契數(shù) F00;F11 for i2 to n do FiFi-1+Fi-2 return F(n)根本操作次數(shù)是多少？ 算法要做n-1次加法運(yùn)算?？臻g效率分析： 沒有必要特意運(yùn)用一個(gè)數(shù)組在存儲(chǔ)斐波那契數(shù)列的前面元素：為了完成該義務(wù)，只需求存儲(chǔ)兩個(gè)元素就足夠了。61算法3 效率類型為(logn)基于等式62遞推關(guān)系的一些求解方法P358 附錄B1 前向替代法x(n)=2x(n-1)+1x(1)=1 x(2)=3 x(3)=7 x(4

21、)=15找規(guī)律：x(n)=2n-1632 反向替代法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 =n643 二階常系數(shù)線性遞推式方式：ax(n)+bx(n-1)+cx(n-2)=f(n)a,b,c是實(shí)數(shù)，a不為0f(n)=0 齊次遞推式65ax(n)+bx(n-1)+cx(n-2)=0的特征方程ar2+br+c=0定理1 設(shè)r1，r2是特征方程的兩個(gè)根第一種情況：假設(shè)r1和r2是不等的實(shí)根 第二種情況：r1和r2相等第三種情況：r1和r2是兩個(gè)不相等的復(fù)數(shù)66例子，斐波那契數(shù)算法1時(shí)間效率遞歸式的計(jì)算當(dāng)n1時(shí)，A(n)=A(n-1)+A(n-2)+1A(0)=0 , A(1)=0改寫A(n)+1-A(n-1)+1-A(n-2)+1=0交換B(n)=A(n)+1 B(n)-B(n-1)-B(n-2)=0 B(0)=1 , B(1)=1 那么 特征方程是 r2-r-1=0根為