算法效率分析基礎(chǔ)教學(xué)參考.ppt

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

2、最壞情況 什么是最好情況,在表A中查找關(guān)鍵字x,5,6,7,8,2.1 分析框架,如何評(píng)價(jià)時(shí)間效率？ 2.1.1 輸入規(guī)模的度量 一個(gè)事實(shí)：?jiǎn)栴}規(guī)模越大，算法運(yùn)行時(shí)間越長(zhǎng)。 將算法輸入規(guī)模n為時(shí)間效率的參數(shù)。 選擇哪個(gè)（些）參數(shù)作為輸入規(guī)模？,9,一個(gè)算法好不好體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少上 所需資源越少，該算法越好； 計(jì)算機(jī)最重要的資源是 時(shí)間和空間 算法分析對(duì)算法利用這兩種資源的效率做研究 時(shí)間效率：指出正在討論的算法運(yùn)行得有多快； 空間效率：關(guān)心算法需要的額外空間。 研究實(shí)驗(yàn)告訴我們，對(duì)于大多數(shù)問(wèn)題來(lái)說(shuō)，我們?cè)谒俣壬夏軌蛉〉玫倪M(jìn)展要遠(yuǎn)大于在空間上的進(jìn)展， 所以我們把主要精力集

3、中在時(shí)間效率上。,10,2.1.2 運(yùn)行時(shí)間的度量單位 可以采用秒，分，小時(shí)嗎？ 可以統(tǒng)計(jì)算法每一步的操作次數(shù)嗎？ 一般的做法： 把基本操作（最重要的操作）次數(shù)作為算法運(yùn)行時(shí)間的度量單位。 思考下面算法的重要操作： 排序 矩陣乘法,11,建立一個(gè)算法時(shí)間效率的分析框架 對(duì)于輸入規(guī)模為n的算法 統(tǒng)計(jì)基本操作執(zhí)行次數(shù)C(n)，來(lái)對(duì)其效率進(jìn)行度量。 在某個(gè)特定計(jì)算機(jī)上的某個(gè)算法程序的運(yùn)行時(shí)間 T(n)copC(n),基本操作的執(zhí)行時(shí)間,基本操作次數(shù),12,對(duì)下面的三個(gè)時(shí)間效率函數(shù)表達(dá)式, 哪一個(gè)效率高? C1(n)=n C2(n)=n3 C3(n)= 10n n=1 1 1 10 n=2 2 8 1

4、00 n=3 3 27 1000 n=非常大,結(jié)論： 1 隨n的遞增，不同函數(shù)增幅不同 2 某些函數(shù)在大規(guī)模時(shí)增幅顯著，函數(shù)可以表示增幅的特點(diǎn) 3 我們希望選擇大規(guī)模時(shí)，時(shí)間效率增幅小的算法,13,2.1.3增長(zhǎng)次數(shù)（增長(zhǎng)幅度） 特別考慮大規(guī)模的輸入要強(qiáng)調(diào)執(zhí)行次數(shù)的增長(zhǎng)次數(shù)呢？這是因?yàn)樾∫?guī)模輸入在運(yùn)行時(shí)間上差別不足以將高效的算法和低效的算法法區(qū)分開(kāi)來(lái)。,14,圖12 各種函數(shù)的曲線,15,2.1.4 算法的最優(yōu)、最差和平均效率 一個(gè)算法的最差效率是指當(dāng)輸入規(guī)模為n時(shí)，算法的最壞情況下的效率。這時(shí)，相對(duì)于其他規(guī)模為n的輸入，該算法的運(yùn)行時(shí)間最長(zhǎng)。 為什么要考慮最壞效率？ 提供了對(duì)任何規(guī)模為n的實(shí)

5、例，算法運(yùn)行的上界Cworst(n),16,一個(gè)算法的最優(yōu)效率是指當(dāng)輸入規(guī)模為n時(shí)，算法在最優(yōu)情況下的效率。這時(shí)，與其它規(guī)模為n的輸入相比，該算法運(yùn)行得最快。 然而，無(wú)論是最差效率分析還是最優(yōu)效率分析都不能提供一種必要的信息：在“典型”或者“隨機(jī)”輸入的情況下， 一個(gè)算法會(huì)具有什么樣的行為。這正是平均效率試圖提供給我們信息。,17,算法計(jì)算復(fù)雜度的定義,18,2.1.5 分析框架概要 算法的時(shí)間效率和空間效率都用輸入規(guī)模的函數(shù)進(jìn)行度量。 我們用算法基本操作的執(zhí)行次數(shù)來(lái)度量算時(shí)間效率。通過(guò)計(jì)算算法消耗的額外存儲(chǔ)單元的數(shù)量來(lái)度量空間效率。 在輸入規(guī)模相同的情況下，有些算法的效率會(huì)的顯著差異。對(duì)于這

6、樣的算法，我們需要區(qū)分最差效率，平均效率和最優(yōu)效率。 本框架主要關(guān)心，當(dāng)算法的輸入規(guī)模趨向于無(wú)限大的時(shí)候，其運(yùn)行時(shí)間（消耗的額外空間）函數(shù)的增長(zhǎng)次數(shù)。,19,復(fù)雜度函數(shù)的階,2.2 漸進(jìn)符號(hào)和基本效率類型,20,21,例題,22,23,注意,上面3個(gè)符號(hào) O， 稱為漸進(jìn)符號(hào) 在問(wèn)題的求解規(guī)模充分大的時(shí)候才成立。 如，N3c的時(shí)候才成立，其中c是方程N(yùn)32N 的解。當(dāng)N c時(shí)，前者反而有效。,24,2.2.5漸進(jìn)符號(hào)的有用特性 定理 如果t1(n) O(g1(n) 并且t2(n) O(g2(n)， 則 t1(n)+ t2(n)O(maxg1(n), g2(n) (對(duì)于和符號(hào)，類似的斷言也為真)

7、對(duì)于兩個(gè)連續(xù)執(zhí)行部分組成的算法，應(yīng)該如何應(yīng)用這個(gè)特性呢？它意味著該算法的整體效率是由具有較大的增長(zhǎng)次數(shù)的部分所決定的，即它的效率較差的部分.,25,2.2.6 利用極限比較增長(zhǎng)次數(shù) 雖然符號(hào)O， 和的正式定義對(duì)于證明它們的抽象性質(zhì)是不可缺少的，但我們很少直接用它們來(lái)比較兩個(gè)特定函數(shù)的增長(zhǎng)次數(shù)。有一種較為簡(jiǎn)便的比較方法，它是基于對(duì)所計(jì)論的兩個(gè)函數(shù)的比率求極限。有3種極限情況會(huì)發(fā)生：,26,2.2.7基本的效率類型,O(2n),O(n!),O(nn),常見(jiàn)的指數(shù)階,O(1),O(logn),O(n),O(nlogn),O(n2),O(n3) ,27,關(guān)于漸進(jìn)時(shí)間效率：,當(dāng)比較兩個(gè)算法的效率時(shí),若兩

8、個(gè)算法是同階的,必須進(jìn)一步考察階的常數(shù)因子才能辨別優(yōu)劣。,28,2.3非遞歸算法的復(fù)雜度分析,如何用前面介紹的知識(shí)分析一個(gè)算法的效率,29,算法分析例題,30,例1 考慮從n個(gè)元素的列表中查找元素最大值的問(wèn)題. 假設(shè)列表是用數(shù)組實(shí)現(xiàn)的。 MaxElement(A0.n-1) /求給定數(shù)組中最大元素的值 /輸入：實(shí)數(shù)數(shù)組A0.n-1 /輸出:A中最大元素的值 maxvalA0; for i1 to n-1 do if Aimaxval maxvalAi; return maxval;,第一步： 決定用哪個(gè)(哪些)參數(shù)作為輸入規(guī)模的度量： 數(shù)組元素的個(gè)數(shù)n,31,MaxElement(A0.n-1

9、) /求給定數(shù)組中最大元素的值 /輸入：實(shí)數(shù)數(shù)組A0.n-1 /輸出:A中最大元素的值 maxvalA0； for i1 to 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 maxval,33,第四步： 建

10、立一個(gè)算法基本操作執(zhí)行次數(shù)的求和表達(dá)式：,MaxElement(A0.n-1) /求給定數(shù)組中最大元素的值 /輸入：實(shí)數(shù)數(shù)組A0.n-1 /輸出:A中最大元素的值 maxvalA0； for i1 to n-1 do if Aimaxval maxvalAi； return maxval,34,把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. 找出算法的

11、基本操作（作為一規(guī)律，它總是位于算法的最內(nèi)層循環(huán)中）。 檢查基本操作的執(zhí)行次數(shù)是否只依賴輸入規(guī)模。如果它還依賴一些其他的特性，則最差效率、平均效率以及最優(yōu)效率（如果必要）需要分別研究。 建立一個(gè)算法基本操作執(zhí)行次數(shù)的求和表達(dá)式。 利用求和運(yùn)算的標(biāo)公式和法則來(lái)建立一個(gè)操作次數(shù)的閉合公式，或者至少確定它的增長(zhǎng)次數(shù)。,37,例2 元素唯一性問(wèn)題：驗(yàn)證給定數(shù)組中的元素是否全部唯一（互不相等）。 UniqueElements(A0.n-1) /輸入：數(shù)組A0.n-1 /輸出：如果A中的元素全部唯一，返回“true” / 否則，返回“false”. for i0 to n-2 do for ji+1 to

12、 n-1 do if Ai=Aj return false Return true,第一步： 決定用哪個(gè)(哪些)參數(shù)作為輸入規(guī)模的度量： 數(shù)組元素的個(gè)數(shù)n,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,第二步： 找出算法基本操作： 比較,39,UniqueElements(A0.n-1) for i0 to n-2 do for ji+1 to n-1 do if Ai=Aj return false Return true,第三步： 檢查基本操作的

13、執(zhí)行次數(shù)是否只依賴輸入規(guī)模： 比較的次數(shù)取決于： n？ 相同元素？ 及其位置？,40,最差效率： 某個(gè)數(shù)組Cworst(n)所做的比較數(shù)比其它數(shù)組都多。 有哪兩種類型？ 不包括相同元素 最后兩個(gè)元素是唯一一對(duì)相同元素,41,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è)算法基本操作執(zhí)行次數(shù)的求和表達(dá)式：,42,這個(gè)結(jié)果是完全可以預(yù)測(cè)的：在最壞的情況下，對(duì)于n個(gè)元素的所有n(n-1)/2對(duì)兩兩組合，該算法都要比較一遍。,總共有0到n-2個(gè)元

14、素需要考察,內(nèi)循環(huán)的一次操作,對(duì)于給定的i內(nèi)循環(huán)從 i+1到n-1進(jìn)行比較,43,例3 給定n階方陣A和B計(jì)算乘積C=AB Algorithm 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； end of for end of for end of for Return C,44,前面3道例題，似乎很簡(jiǎn)單 但在某些時(shí)候會(huì)有困難： 循環(huán)變量無(wú)規(guī)律變化，過(guò)于復(fù)雜而無(wú)法求解的求和表達(dá)式，分析平均情況的難

15、度等。,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)的值， 求n,46,2.4 遞歸算法的復(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本身來(lái)指出算法的輸入規(guī)模 該算法的基本操作是乘

16、法，它的執(zhí)行次數(shù)記作M(n)，思考應(yīng)該如何構(gòu)造表達(dá)式?,47,用到的乘法數(shù)量M(n)需要滿足這個(gè)等式： 當(dāng)n0時(shí)，M(n)= M(n-1)+ 1 if n=0 return 1 else return F(n-1)*n,規(guī)模為n的階乘的乘法數(shù)量,做一次乘法F(n-1)*n,做完一次乘法后，階乘規(guī)模變?yōu)閚-1,48,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 =n,初始條件M(0)=0,if n=0 return 1 else return F(n-1)*n,49,分析遞歸算法效率的通用方案 決定用哪個(gè)（

17、哪些）參數(shù)作為輸入規(guī)模的度量。 找出算法的基本操作。 檢查一下，對(duì)于相同規(guī)模的不同輸入，基本操作的執(zhí)行次數(shù)是否不同。如果不同，則必須對(duì)最差效率、平均效率以及最優(yōu)效率作單獨(dú)研究。 對(duì)于算法基本操作的執(zhí)行次數(shù)，建立一個(gè)遞推關(guān)系以及相應(yīng)的初始條件。 解這個(gè)遞推式，或者至少確定它有解的增長(zhǎng)次數(shù)。,50,例2 漢諾塔問(wèn)題. 三根柱子A,B,C, 在A上有n個(gè)半徑不同的中間有孔的圓盤(pán), 從下而上半徑遞減. 按照下述規(guī)則將所有盤(pán)子從源盤(pán)A搬到目的C, 將B做輔助過(guò)渡: 一次只能搬動(dòng)一個(gè)盤(pán)子 任何時(shí)候大盤(pán)子不能在小盤(pán)子上面,51,解決思路 n=1時(shí), 搬動(dòng)一個(gè)盤(pán)子即可; n1時(shí), 分三步執(zhí)行. (1)將n1個(gè)

18、盤(pán)子(最大的 除外)從源移至輔助柱; (2)將最大盤(pán)從源移至目的; (3)將在輔助柱上的n1 個(gè)盤(pán)子移至目的柱. 問(wèn)題規(guī)模是什么？ 基本操作是什么？ 時(shí)間效率表達(dá)式？,52,分析： 1、算法可以直接給出的解答是當(dāng)n=1時(shí)，需要一個(gè)單位時(shí)間的工作量,M(1)=1 2、 第一步和第三步都是將n1個(gè)盤(pán)子從一個(gè)柱移到另一個(gè)，所以移n個(gè)盤(pán)子的問(wèn)題可以分成2個(gè)移n1個(gè)盤(pán)子的問(wèn)題。 3 、其余的工作量：第二步需要一個(gè)單位時(shí)間的工作量。 M(1) = 1,(n =1) M(n)= 2 M(n-1) +1, (n1),53,M(n)=2 M(n-1) +1 =2(2M(n-2)+1)+1 =22M(n-2)+2

19、+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-1,54,前面的例子： 求一個(gè)十進(jìn)制正整數(shù)在二進(jìn)制表示中的二進(jìn)制數(shù)字個(gè)數(shù) Binary(n) /輸入正整數(shù)n Count=1 While n1 do count=count+1 n= Return count,遞歸版本 BinRec(n) If n=1 return 1 Else return BinRec( )+1,55,2.5 例題：斐波那契數(shù)列,目的： 1、 說(shuō)明計(jì)算斐波那契數(shù)的算法以及效率分析

20、 2、 說(shuō)明算法分析中遞推關(guān)系的一些求解方法 （P357 附錄B）,56,斐波那契數(shù)列0,1,1,2,3,5,8,13,21,34, 觀察特點(diǎn)是什么？ 從第3個(gè)數(shù)開(kāi)始每一個(gè)數(shù)是前兩個(gè)數(shù)之和。 如何寫(xiě)成遞推式？： 當(dāng)n1時(shí)，F(xiàn)(n)=F(n-1)+F(n-2) F(0)=0,F(1)=1,注意： 后面問(wèn)題的n均從0開(kāi)始。,57,算法1 F(n) /根據(jù)定義，遞歸計(jì)算第n個(gè)斐波那契數(shù) /輸入：一個(gè)非負(fù)整數(shù)n /輸出：第n個(gè)斐波那契數(shù) if n1 return n else return F(n-1)+F(n-2) 用什么做問(wèn)題規(guī)模？ 基本操作？ 是否有其他因素影響基本操作次數(shù)？ 寫(xiě)成遞推式。,58

21、,if n1 return n else return F(n-1)+F(n-2) 當(dāng)n1時(shí)，A(n)=A(n-1)+A(n-2)+1 A(0)=0 , A(1)=0,59,當(dāng)n1時(shí)，A(n)=A(n-1)+A(n-2)+1 對(duì)該遞歸式的分析 1 采用估計(jì)的方式 2 采用精確計(jì)算方式(后面說(shuō)明),效率不高的原因:重復(fù)計(jì)算相同的函數(shù)值.,60,改進(jìn)思想： 通過(guò)簡(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

22、(n) 基本操作次數(shù)是多少？ 算法要做n-1次加法運(yùn)算。 空間效率分析： 沒(méi)有必要特意使用一個(gè)數(shù)組在存儲(chǔ)斐波那契數(shù)列的前面元素：為了完成該任務(wù)，只需要存儲(chǔ)兩個(gè)元素就足夠了。,61,算法3 效率類型為(logn) 基于等式,62,遞推關(guān)系的一些求解方法,P358 附錄B 1 前向替代法 x(n)=2x(n-1)+1 x(1)=1 x(2)=3 x(3)=7 x(4)=15 找規(guī)律：x(n)=2n-1,63,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 =n,64,3 二階常系數(shù)線性遞推式 形

23、式：ax(n)+bx(n-1)+cx(n-2)=f(n) a,b,c是實(shí)數(shù)，a不為0 f(n)=0 齊次遞推式,65,ax(n)+bx(n-1)+cx(n-2)=0的特征方程ar2+br+c=0 定理1 設(shè)r1，r2是特征方程的兩個(gè)根 第一種情況：如果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)+1 A(0)=0 , A(1)=0 改寫(xiě)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 根為 前面第1種情況,67,兩值的計(jì)算依賴于B(n)的初始值B(0)=1 , B(1)=1 最后得,68,算法分析中的常見(jiàn)遞推類型,減一法: T(n)=T(n-1)+f(n) 減常因子： T(n)=T(n/b)+f(n) 分治法： T(n)=aT(n/b)+f(n),69,2.6 算法的經(jīng)驗(yàn)分析,很多貌似簡(jiǎn)單的算法