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

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

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

3、計算法每一步的操作次數(shù)嗎？普通的做法：把根本操作最重要的操作次數(shù)作為算法運轉(zhuǎn)時間的度量單位。思索下面算法的重要操作：排序矩陣乘法11建立一個算法時間效率的分析框架對于輸入規(guī)模為n的算法統(tǒng)計根本操作執(zhí)行次數(shù)C(n)，來對其效率進展度量。在某個特定計算機上的某個算法程序的運轉(zhuǎn)時間T(n)copC(n)根本操作的執(zhí)行時間根本操作次數(shù)12對下面的三個時間效率函數(shù)表達式, 哪一個效率高?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ù)可以表示增幅的

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

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

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

7、它們的籠統(tǒng)性質(zhì)是不可短少的，但我們很少直接用它們來比較兩個特定函數(shù)的增長次數(shù)。有一種較為簡便的比較方法，它是基于對所計論的兩個函數(shù)的比率求極限。有3種極限情況會發(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;第一步：決議用哪個(哪些)參數(shù)作為輸入規(guī)模的度量：數(shù)組元素的個數(shù)n31MaxElement(A0.n-1) /求給定數(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ù)組A0.n-1 /輸出:A中最大元素的值 maxvalA0； for i1 to n-1 do if Aimaxval maxvalAi； return maxval33第四步：建立一個算法根本操作執(zhí)行次數(shù)的求和表達式：MaxElement(A0.n-1) /求給定數(shù)組中最大元素的值 /輸入：實數(shù)數(shù)組A0.n-1 /輸出:A中最大

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

10、別研討。建立一個算法根本操作執(zhí)行次數(shù)的求和表達式。利用求和運算的標公式和法那么來建立一個操作次數(shù)的閉合公式，或者至少確定它的增長次數(shù)。37例2 元素獨一性問題：驗證給定數(shù)組中的元素能否全部獨一互不相等。UniqueElements(A0.n-1)/輸入：數(shù)組A0.n-1/輸出：假設(shè)A中的元素全部獨一，前往“true/ 否那么，前往“false. for i0 to n-2 do for ji+1 to n-1 do if Ai=Aj return falseReturn true第一步：決議用哪個(哪些)參數(shù)作為輸入規(guī)模的度量：數(shù)組元素的個數(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最差效率：某個數(shù)組Cworst(n)所做的比較數(shù)比其它數(shù)組都多。有哪兩種類型？不包括一樣元素最后兩個元素是獨一一對一樣元素41UniqueElements(

12、A0.n-1)for i1 to n-2 do for ji+1 to n-1 do if Ai=Aj return falseReturn true第四步：建立一個算法根本操作執(zhí)行次數(shù)的求和表達式：42這個結(jié)果是完全可以預(yù)測的：在最壞的情況下，對于n個元素的一切n(n-1)/2對兩兩組合，該算法都要比較一遍?？偣灿?到n-2個元素需求調(diào)查內(nèi)循環(huán)的一次操作對于給定的i內(nèi)循環(huán)從i+1到n-1進展比較43例3 給定n階方陣A和B計算乘積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道例題，似乎很簡單但在某些時候會有困難：循環(huán)變量無規(guī)律變化，過于復(fù)雜而無法求解的求和表達式，分析平均情況的難度等。45例4 設(shè)計算法求一個十進制正整數(shù)在二進制表示中的二進制數(shù)字個數(shù)， 并分析算法的計算復(fù)雜度算法思想Binary(n)/輸入十進制正整數(shù)n count :=1 While n1 do count := count+1 n :=Return count給定f(x)的值， 求n462.4 遞

14、歸算法的復(fù)雜度分析例1 對于恣意非負整數(shù)n,計算階乘函數(shù)F(n)=n!的值。 當n1時，F(xiàn)(n)=F(n-1)n 且0!=1算法 F(n) /輸入：非負整數(shù)n if n=0 return 1 else return F(n-1)*n用n本身來指出算法的輸入規(guī)模該算法的根本操作是乘法，它的執(zhí)行次數(shù)記作M(n)，思索應(yīng)該如何構(gòu)造表達式?47用到的乘法數(shù)量M(n)需求滿足這個等式： 當n0時，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分析遞歸算法效率的通用方案決議用哪個哪些參數(shù)作為輸入規(guī)模的度量。找出算法的根本操作。檢查一下，對于一樣規(guī)模的不同輸入，根本操作的執(zhí)行次數(shù)能否不同。假設(shè)不同，那么必需對最差效率、平均效率以及最優(yōu)效率作單獨研討。對于算法根本操作的執(zhí)行次數(shù)，建立一個遞推關(guān)系以及相應(yīng)的初始條件。解這個遞推式，或者至少確定它有解的增長次數(shù)。50例2 漢諾塔問題. 三根柱子A,B,C, 在A上有n個半徑不同

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

17、第二步需求一個單位時間的任務(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前面的例子： 求一個十進制正整數(shù)在二進制表示中的二進制數(shù)字個數(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、 闡明計算斐波那契數(shù)的算法以及效率分析2、 闡明算法分析中遞推關(guān)系的一些求解方法 P357 附錄B56斐波那契數(shù)列0,1,1,2,3,5,8,13,21,34,察看特點是什么？從第3個數(shù)開場每一個數(shù)是前兩個數(shù)之和。如何寫成遞推式？： 當n1時，F(xiàn)(n)=F(n-1)+F(n-2) F(0)=0,F(1)=1留意：后面問題的n均從0開場。57算法1 F(n)/根據(jù)定義，遞歸計算第n個斐波那契數(shù)/輸入：一個非負整數(shù)n/輸出：第n個斐波那契數(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)當n1時，A(n)=A(n-1)+A(n-2)+1A(0)=0 , A(1)=0 59當n1時，A(n)=A(n-1)+A(n-2)+1對該遞歸式的分析1 采用估計的方式2 采用準確計算方式(后面闡明)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ù)的遞歸調(diào)用樹效率不高的緣由:反復(fù)計算一樣的

20、函數(shù)值.60改良思想：經(jīng)過簡單地對斐波那契數(shù)列的延續(xù)元素進展迭代計算算法2 Fib(n)/根據(jù)定義，迭代計算第n個斐波那契數(shù)/輸入：一個非負整數(shù)n/輸出：第n個斐波那契數(shù) F00;F11 for i2 to n do FiFi-1+Fi-2 return F(n)根本操作次數(shù)是多少？ 算法要做n-1次加法運算?？臻g效率分析： 沒有必要特意運用一個數(shù)組在存儲斐波那契數(shù)列的前面元素：為了完成該義務(wù)，只需求存儲兩個元素就足夠了。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ù)，a不為0f(n)=0 齊次遞推式65ax(n)+bx(n-1)+cx(n-2)=0的特征方程ar2+br+c=0定理1 設(shè)r1，r2是特征方程的兩個根第一種情況：假設(shè)r1和r2是不等的實根 第二種情況：r1和r2相等第三種情況：r1和r2是兩個不相等的復(fù)數(shù)66例子，斐波那契數(shù)算法1時間效率遞歸式的計算當n1時，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根為