算法設(shè)計(jì)與分析基礎(chǔ)第2版算法分析第2章-課件

第2章算法效率分析基礎(chǔ)我常常說，當(dāng)你對(duì)所講的內(nèi)容能夠進(jìn)行度量并且能夠用數(shù)字來表達(dá)時(shí)，證明你對(duì)這些內(nèi)容是有所了解的；如果你不能用數(shù)字來表達(dá)，那么你的認(rèn)識(shí)是不完整的，也是無法令人滿意的.-------LordKelvin(1824-1907)

第2章算法效率分析基礎(chǔ)我常常說，當(dāng)你對(duì)所講的內(nèi)12.1分析框架在本節(jié)中,我們將概要地描述一個(gè)分析算法效率的一般性框架.首先必須指出,有兩種算法效率:時(shí)間效率和空間效率。時(shí)間效率指出正在討論的算法運(yùn)行得有多快；空間效率關(guān)心算法需要的額外空間。研究實(shí)驗(yàn)告訴我們，對(duì)于大多數(shù)問題來說，我們?cè)谒俣壬夏軌蛉〉玫倪M(jìn)展要遠(yuǎn)大于在空間上的進(jìn)展，所以我們把主要精力集中在時(shí)間效率上。2.1分析框架在本節(jié)中,我們將概要地描述一個(gè)分析算法效率的22.1.1輸入規(guī)模的度量幾乎所有的算法，對(duì)于規(guī)模更大的輸入都需要?jiǎng)有懈L(zhǎng)的時(shí)間。例如，需要更多時(shí)間來對(duì)更長(zhǎng)的數(shù)組排序，更大的矩陣相乘也需要花費(fèi)更多時(shí)間，等等。所以，使用一個(gè)以算法輸入規(guī)模式n為參數(shù)的函數(shù)，來研究算法效率是非常合乎邏輯的。2.1.1輸入規(guī)模的度量32.1.2運(yùn)行時(shí)間的度量單位

我們把基本操作作為算法運(yùn)行時(shí)間的度量單位。所謂基本操作，就是算法中最重要的操作。它們對(duì)總運(yùn)行時(shí)間的貢獻(xiàn)最大。我們的下一步工作就是計(jì)算它們的運(yùn)行次數(shù)。掌握了這樣一種規(guī)律，我們就不難發(fā)現(xiàn)一個(gè)算法中的基本操作：它通常是算法最內(nèi)層循環(huán)中最費(fèi)時(shí)的操作。例如，大多數(shù)排序算法是通過比較列表中的待排序元素（鍵）來進(jìn)行工作的；對(duì)于這種算法來說，基本操作就是對(duì)鍵的比較。

2.1.2運(yùn)行時(shí)間的度量單位42.1.3增長(zhǎng)次數(shù)

為什么對(duì)于大規(guī)模的輸入要強(qiáng)調(diào)執(zhí)行次數(shù)的增長(zhǎng)次數(shù)呢？這是因?yàn)樾∫?guī)模輸入在運(yùn)行時(shí)間上差別不足以將高效的算法和低效的算法法區(qū)分開來。

2.1.3增長(zhǎng)次數(shù)

為什么對(duì)于大規(guī)模的輸入要強(qiáng)調(diào)執(zhí)5算法設(shè)計(jì)與分析基礎(chǔ)第2版算法分析第2章-課件62.1.4算法的最優(yōu)、最差和平均效率一個(gè)算法的最差效率是指當(dāng)輸入規(guī)模為n時(shí)，算法的最壞情況下的效率。這時(shí)，相對(duì)于其他規(guī)模為n的輸入，該算法的運(yùn)行時(shí)間最長(zhǎng)。一個(gè)算法的最優(yōu)效率是指當(dāng)輸入規(guī)模為n時(shí)，算法在最優(yōu)情況下的效率。這時(shí)，與其它規(guī)模為n的輸入相比，該算法運(yùn)行得最快。然而，無論是最差效率分析還是最優(yōu)效率分析都不能提供一種必要的信息：在“典型”或者“隨機(jī)”輸入的情況下，一個(gè)算法會(huì)具有什么樣的行為。這正是平均效率試圖提供給我們信息。還有一種類型的效率稱為攤銷效率。它并不適用于算法的單次運(yùn)行，而是應(yīng)用于算法對(duì)同樣數(shù)據(jù)結(jié)構(gòu)所執(zhí)行的一系列操作。2.1.4算法的最優(yōu)、最差和平均效率72.1.5分析框架概要算法的時(shí)間效率和空間效率都用輸入規(guī)模的函數(shù)進(jìn)行度量。我們用算法基本操作的執(zhí)行次數(shù)來度量算時(shí)間效率。通過計(jì)算算法消耗的額外存儲(chǔ)單元的數(shù)量來度量空間效率。在輸入規(guī)模相同的情況下，有些算法的效率會(huì)的顯著差異。對(duì)于這樣的算法，我們需要區(qū)分最差效率，平均效率和最優(yōu)效率。本框架主要關(guān)心，當(dāng)算法的輸入規(guī)模趨向于無限大的時(shí)候，其運(yùn)行時(shí)間（消耗的額外空間）函數(shù)的增長(zhǎng)次數(shù)。2.1.5分析框架概要82.2漸進(jìn)符號(hào)和基本效率類型2.2.1非正式的介紹非正式來說，O(g(n))是增長(zhǎng)次數(shù)小于等于是g(n)(以及其常數(shù)倍，n趨向于無窮大)的函數(shù)集合。n∈O(n2),100n+5∈O(n2),1/2(n(n-1))∈O(n2),n3∈/O(n2),第二個(gè)符號(hào)?(g(n))，代表增長(zhǎng)次數(shù)大于等于g(n)(以及其常數(shù)倍,n趨向于無窮大)的函數(shù)集合。

n3∈?(n2)，1/2(n(n-1))∈?(n2)，但是100n+5∈/?(n2)最后，Θ(g(n))是增長(zhǎng)次數(shù)等于g(n))(以及其常數(shù)倍,n趨向于無窮大)的函數(shù)集合。因些，每一個(gè)二次方程an2+bn+c在a>0的情況下都包含在Θ(n2)中，除了無數(shù)類似于n2+sinn和n2+logn的函數(shù)（你能解釋原因嗎？）。2.2漸進(jìn)符號(hào)和基本效率類型2.2.1非正式的介紹92.2.2符號(hào)О

定義1我們把函數(shù)t(n)屬于O(g(n))，記作t(n)∈

O(g(n));它的成立條件是：對(duì)于所有足夠大的n，t(n)的上界由g(n)的常數(shù)倍數(shù)所確定，也就是說，存在大于0的常數(shù)c和非負(fù)的整數(shù)n0，使得：對(duì)于所有的n≥n0來說，t(n)≤cg(n)n0之前的情況無關(guān)重要cg(n)t(n)n符號(hào)O：t(n)∈O(g(n))n02.2.2符號(hào)Оn0之前的情況無關(guān)重要cg(n)t(n)n102.2.3符號(hào)?定義2我們把函數(shù)t(n)屬于?(g(n))，記作t(n)∈?(g(n))，它的成立條件是：對(duì)于所有足夠大的n，t(n)的下界由g(n)的常數(shù)倍所確定，也就是說，存在大于0的常數(shù)c和非負(fù)的整數(shù)n0，使得：對(duì)于所有的n≥n0來說，t(n)≥cg(n)n0之前的情況無關(guān)重要cg(n)t(n)n符號(hào)?：t(n)∈?(g(n))n02.2.3符號(hào)?n0之前的情況無關(guān)重要cg(n)t(n)n112.2.4符號(hào)Θ定義3我們把函數(shù)t(n)屬于Θ(g(n))，記作t(n)∈Θ(g(n));它的成立條件是：對(duì)于所有足夠大的n，t(n)的上界和下界都由g(n)的常數(shù)倍數(shù)所確定，也就是說，存在大于0的常數(shù)c1，c2和和非負(fù)的整數(shù)n0，使得：對(duì)于所有的n≥n0來說，c2g(n)≤t(n)≤c1g(n)n0之前的情況無關(guān)重要c1g(n)t(n)n符號(hào)Θ：t(n)∈Θ(g(n))n0c2g(n)2.2.4符號(hào)Θn0之前的情況無關(guān)重要c1g(n)t(n122.2.5漸進(jìn)符號(hào)的有用特性定理如果t1(n)∈O(g1(n))并且t2(n)∈O(g2(n))，則t1(n)+t2(n)∈O(max{g1(n),g2(n)})(對(duì)于?和Θ符號(hào)，類似的斷言也為真)對(duì)于兩個(gè)連續(xù)執(zhí)行部分組成的算法，應(yīng)該如何應(yīng)用這個(gè)特性呢？它意味著該算法的整體效率是由具有較大的增長(zhǎng)次數(shù)的部分所決定的，即它的效率較差的部分.2.2.5漸進(jìn)符號(hào)的有用特性132.2.6利用極限比較增長(zhǎng)次數(shù)雖然符號(hào)O，?和Θ的正式定義對(duì)于證明它們的抽象性質(zhì)是不可缺少的，但我們很小直接用它們來比較兩個(gè)特定函數(shù)的增長(zhǎng)次數(shù)。有一種較為簡(jiǎn)便的比較方法，它是基于對(duì)所計(jì)論的兩個(gè)函數(shù)的比率求極限。有3種極限情況會(huì)發(fā)生：2.2.6利用極限比較增長(zhǎng)次數(shù)142.2.7基本的效率類型

1constantlognlogarithmicnlinearnlognnlognn2quadraticn3cubic2nexponentialn!factorial2.2.7基本的效率類型1constantlognloga15練習(xí)Problem2,4.b,5,and6.aP48練習(xí)Problem2,4.b,5,and6.a162.3非遞歸算法的數(shù)學(xué)分析例1考慮一下從n個(gè)元素的列表中查找元素最大值的問題.簡(jiǎn)單起見,我們假設(shè)列表是用數(shù)組實(shí)現(xiàn)的。下面給出一個(gè)解決問題的標(biāo)準(zhǔn)算法的偽代碼。算法MaxElement(A[0..n-1])

//求給定數(shù)組中最大元素的值//輸入：實(shí)數(shù)數(shù)組A[0..n-1]//輸出：A中最大元素的值maxval←A[0]fori←1ton-1doifA[i]>maxvalmaxval←A[i]returnmaxval2.3非遞歸算法的數(shù)學(xué)分析例1考慮一下從n個(gè)元素的列表中查17如何確定基本操作呢？由于做每一次循環(huán)都會(huì)進(jìn)行一次比較，所以把比較作為基本操作如何確定基本操作呢？18我們把C(n)記作比較運(yùn)算的執(zhí)行次數(shù),并試圖尋找一個(gè)公式將它表達(dá)為規(guī)模n的函數(shù)。由于該算法每執(zhí)行一次循環(huán)就會(huì)做一次比較，并且對(duì)于循環(huán)變量i在1和n-1(包含在內(nèi))中的每個(gè)值都會(huì)做一次循環(huán)，所以，我們得到C(n)的下列求和表達(dá)式：

我們把C(n)記作比較運(yùn)算的執(zhí)行次數(shù),并試圖尋找一個(gè)19分析非遞歸算法效率的通用方案1.決定用哪個(gè)(哪些)參數(shù)作為輸入規(guī)模的度量2.找出算法的基本操作（作為一規(guī)律，它總是位于算法的最內(nèi)層循環(huán)中）。檢查基本操作的執(zhí)行次數(shù)是否只依賴輸入規(guī)模。如果它還依賴一些其他的特性，則最差效率、平均效率以及最優(yōu)效率（如果必要）需要分別研究。建立一個(gè)算法基本操作執(zhí)行次數(shù)的求和表達(dá)式。利用求和運(yùn)算的標(biāo)公式和法則來建立一個(gè)操作次數(shù)的閉合公式，或者至少確定它的增長(zhǎng)次數(shù)。分析非遞歸算法效率的通用方案1.決定用哪個(gè)(哪些)參20例2考慮一下元素惟一性問題：驗(yàn)證給定數(shù)組中的元素是否全部惟一。下面這個(gè)簡(jiǎn)單直接的算法可以解決該問題。算法UniqueElements(A[0..n-1])//驗(yàn)證給定數(shù)組中的無素是否全部惟一//輸入：數(shù)組A[0..n-1]//輸出：如果A中的元素全部惟一，返回“true”//否則，返回“false”.fori←1ton-2doforj←i+1ton-1doifA[i]=A[j]returnfalseReturntrue例2考慮一下元素惟一性問題：驗(yàn)證給定數(shù)組中的元素是否全部惟21基本操作：比較除了和n有關(guān)外，還取決于數(shù)組中是否有相同的元素，以及它們?cè)跀?shù)組中的位置必須研究其最優(yōu)，平均和最差效率基本操作：比較22這個(gè)結(jié)果是完全可以預(yù)測(cè)的：在最壞的情況下，對(duì)于n個(gè)元素的所有n(n-1)/2對(duì)兩兩組合，該算法都要比較一遍。這個(gè)結(jié)果是完全可以預(yù)測(cè)的：在最壞的情況下，對(duì)于n個(gè)元素的所有23矩陣乘法Algorithm

MatrixMultiplication(A[0..n-1,0..n-1],B[0..n-1,0..n-1])//Multipliestwosquarematricesofordernbythedefinition-basedalgorithm//Input:twon-by-nmatricesAandB//Output:MatrixC=ABfori0ton-1do forj0ton–1do C[i,j]0.0 fork0ton–1do C[i,j]C[i,j]+A[i,k]*B[k,j]returnC矩陣乘法AlgorithmMatrixMultiplica24乘法次數(shù)乘法次數(shù)252.4遞歸算法的數(shù)學(xué)分析例1對(duì)于任意非負(fù)整數(shù)n,計(jì)算階乘函數(shù)F(n)=n!的值。因?yàn)楫?dāng)n≥1時(shí)，n!=1·…·(n-1)·n=(n-1)!·n并且根據(jù)定義，0!=1，我們可以使用下面的遞歸算法計(jì)算F(n)=F(n-1)·n2.4遞歸算法的數(shù)學(xué)分析例1對(duì)于任意非負(fù)整數(shù)n,計(jì)算階乘26算法F(n)

//遞歸計(jì)算n!//輸入：非負(fù)整數(shù)n//輸出：n!的值ifn=0return1elsereturnF(n-1)*n我們用n本身來指出算法的輸入規(guī)模（而不是它的二進(jìn)制表示的比特?cái)?shù)）。該算法的基本操作是乘法，我們把它的執(zhí)行次數(shù)記作M(n)。算法設(shè)計(jì)與分析基礎(chǔ)第2版算法分析第2章-課件27因?yàn)楹瘮?shù)F(n)的計(jì)算是根據(jù)下面公式：當(dāng)n>0時(shí)，F(xiàn)(n)=F(n-1)*n所以，計(jì)算這個(gè)公式時(shí)，用到的乘法數(shù)量M(n)需要滿足這個(gè)等式：當(dāng)n>0時(shí)，M(n)=M(n-1)+1的確，計(jì)算F(n-1)需要用M(n-1)次乘法，還有一次乘法用來把該結(jié)果乘法n。為了確定一個(gè)惟一解，我們還需要一初始條件來告訴我們?cè)撔蛄械钠鹗贾怠Ｒ驗(yàn)楹瘮?shù)F(n)的計(jì)算是根據(jù)下面公式：28為了得到這個(gè)起始值，我們可以觀察該算法停止遞歸調(diào)歸調(diào)用時(shí)的條件：ifn=0return1所以，我們所遵循的初始條件是：M(0)=0這樣，我們成功地建立了關(guān)于該算法的乘法次數(shù)M(n)的遞推關(guān)系和初始條件：當(dāng)n>0時(shí)，M(n)=M(n-1)+1M(0)=0最終結(jié)果為M(n)=M(n-1)+1=…=M(n-i)+i=…=M(n-n)+n=n為了得到這個(gè)起始值，我們可以觀察該算法停止遞歸調(diào)歸調(diào)用時(shí)的條29分析遞歸算法效率的通用方案決定用哪個(gè)（哪些）參數(shù)作為輸入規(guī)模的度量。找出算法的基本操作。檢查一下，對(duì)于相同規(guī)模的不同輸入，基本操作的執(zhí)行次數(shù)是否不同。如果不同，則必須對(duì)最差效率、平均效率以及最優(yōu)效率作單獨(dú)研究。對(duì)于算法基本操作的執(zhí)行次數(shù)，建立一個(gè)遞推關(guān)系以及相應(yīng)的初始條件。解這個(gè)遞推式，或者至少確定它有解的增長(zhǎng)次數(shù)。分析遞歸算法效率的通用方案決定用哪個(gè)（哪些）參數(shù)作為輸入規(guī)模30練習(xí)Exercise2.3,P54Problem6Exercise2.4,P61-62Problem1,partb.,c.,e.Problem7練習(xí)Exercise2.3,P54312.5例題：斐波那契數(shù)列斐波那契數(shù)列—0,1,1,2,3,5,8,13,21,34,…這個(gè)數(shù)列可以用一個(gè)簡(jiǎn)單的遞推式和兩個(gè)初始條件來定義：當(dāng)n>1時(shí)，F(xiàn)(n)=F(n-1)+F(n-2)F(0)=0,F(1)=1算法F(n)//根據(jù)定義，遞歸計(jì)算第n個(gè)斐波那契數(shù)//輸入：一個(gè)非負(fù)整數(shù)n//輸出：第n個(gè)斐波那契數(shù)ifn≤returnnelsereturnF(n-1)+F(n-2)2.5例題：斐波那契數(shù)列32該算法的基本操作很明顯是加法，我們把A(n)定義為這個(gè)算法在計(jì)算F(n)的過程中所做的加法次數(shù)。因而，計(jì)算F(n-1)和F(n-2)所需要的加法次數(shù)分別是A(n-1)和A(n-2)，而該算法還需要做一次加法來計(jì)算它們的和。因此，對(duì)于A(n)我們有下面的遞推式：當(dāng)n>1時(shí)，A(n)=A(n-1)+A(n-2)+1從遞推式中，我們可以預(yù)計(jì)到該算法的效率不高。的確，它包含兩個(gè)遞歸調(diào)用，而這兩個(gè)調(diào)用的規(guī)模僅比n略小一點(diǎn)。通過觀察該算法的遞歸調(diào)用樹，我們也能發(fā)現(xiàn)該算法效率低下的原因。相同的函數(shù)值被一遍一遍地重復(fù)計(jì)算，這很明顯是一種效率低下的做法。該算法的基本操作很明顯是加法，我們把A(n)定義為這33F(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(4)F(5)F(3)F(3)F(2)F(2)F(1)F(34通過簡(jiǎn)單地對(duì)斐波那契數(shù)列的連續(xù)元素進(jìn)行迭代計(jì)算，我們得到了一個(gè)快得多的算法，就像下面的這個(gè)算一樣：算法Fib(n)//根據(jù)定義，迭代計(jì)算第n個(gè)斐波那契數(shù)//輸入：一個(gè)非負(fù)整數(shù)n//輸出：第n個(gè)斐波那契數(shù)F[0]←0;F[1]←1fori←2tondoF[i]←F[i-1]+F[i-2]returnF(n)很明顯，這個(gè)算法要做n-1次加法運(yùn)算。所以，它和n一樣都是線性函數(shù)，“僅在”作為n的二進(jìn)制位數(shù)的函數(shù)時(shí)，才表現(xiàn)為指出級(jí)函數(shù)。注意，沒有必要特意使用一個(gè)數(shù)組在存儲(chǔ)斐波那契數(shù)列的前面元素：為了完成該任務(wù)，只需要存儲(chǔ)兩個(gè)元素就足夠了。通過簡(jiǎn)單地對(duì)斐波那契數(shù)列的連續(xù)元素進(jìn)行迭代計(jì)算，我們35第2章算法效率分析基礎(chǔ)我常常說，當(dāng)你對(duì)所講的內(nèi)容能夠進(jìn)行度量并且能夠用數(shù)字來表達(dá)時(shí)，證明你對(duì)這些內(nèi)容是有所了解的；如果你不能用數(shù)字來表達(dá)，那么你的認(rèn)識(shí)是不完整的，也是無法令人滿意的.-------LordKelvin(1824-1907)

第2章算法效率分析基礎(chǔ)我常常說，當(dāng)你對(duì)所講的內(nèi)362.1分析框架在本節(jié)中,我們將概要地描述一個(gè)分析算法效率的一般性框架.首先必須指出,有兩種算法效率:時(shí)間效率和空間效率。時(shí)間效率指出正在討論的算法運(yùn)行得有多快；空間效率關(guān)心算法需要的額外空間。研究實(shí)驗(yàn)告訴我們，對(duì)于大多數(shù)問題來說，我們?cè)谒俣壬夏軌蛉〉玫倪M(jìn)展要遠(yuǎn)大于在空間上的進(jìn)展，所以我們把主要精力集中在時(shí)間效率上。2.1分析框架在本節(jié)中,我們將概要地描述一個(gè)分析算法效率的372.1.1輸入規(guī)模的度量幾乎所有的算法，對(duì)于規(guī)模更大的輸入都需要?jiǎng)有懈L(zhǎng)的時(shí)間。例如，需要更多時(shí)間來對(duì)更長(zhǎng)的數(shù)組排序，更大的矩陣相乘也需要花費(fèi)更多時(shí)間，等等。所以，使用一個(gè)以算法輸入規(guī)模式n為參數(shù)的函數(shù)，來研究算法效率是非常合乎邏輯的。2.1.1輸入規(guī)模的度量382.1.2運(yùn)行時(shí)間的度量單位

我們把基本操作作為算法運(yùn)行時(shí)間的度量單位。所謂基本操作，就是算法中最重要的操作。它們對(duì)總運(yùn)行時(shí)間的貢獻(xiàn)最大。我們的下一步工作就是計(jì)算它們的運(yùn)行次數(shù)。掌握了這樣一種規(guī)律，我們就不難發(fā)現(xiàn)一個(gè)算法中的基本操作：它通常是算法最內(nèi)層循環(huán)中最費(fèi)時(shí)的操作。例如，大多數(shù)排序算法是通過比較列表中的待排序元素（鍵）來進(jìn)行工作的；對(duì)于這種算法來說，基本操作就是對(duì)鍵的比較。

2.1.2運(yùn)行時(shí)間的度量單位392.1.3增長(zhǎng)次數(shù)

為什么對(duì)于大規(guī)模的輸入要強(qiáng)調(diào)執(zhí)行次數(shù)的增長(zhǎng)次數(shù)呢？這是因?yàn)樾∫?guī)模輸入在運(yùn)行時(shí)間上差別不足以將高效的算法和低效的算法法區(qū)分開來。

2.1.3增長(zhǎng)次數(shù)

為什么對(duì)于大規(guī)模的輸入要強(qiáng)調(diào)執(zhí)40算法設(shè)計(jì)與分析基礎(chǔ)第2版算法分析第2章-課件412.1.4算法的最優(yōu)、最差和平均效率一個(gè)算法的最差效率是指當(dāng)輸入規(guī)模為n時(shí)，算法的最壞情況下的效率。這時(shí)，相對(duì)于其他規(guī)模為n的輸入，該算法的運(yùn)行時(shí)間最長(zhǎng)。一個(gè)算法的最優(yōu)效率是指當(dāng)輸入規(guī)模為n時(shí)，算法在最優(yōu)情況下的效率。這時(shí)，與其它規(guī)模為n的輸入相比，該算法運(yùn)行得最快。然而，無論是最差效率分析還是最優(yōu)效率分析都不能提供一種必要的信息：在“典型”或者“隨機(jī)”輸入的情況下，一個(gè)算法會(huì)具有什么樣的行為。這正是平均效率試圖提供給我們信息。還有一種類型的效率稱為攤銷效率。它并不適用于算法的單次運(yùn)行，而是應(yīng)用于算法對(duì)同樣數(shù)據(jù)結(jié)構(gòu)所執(zhí)行的一系列操作。2.1.4算法的最優(yōu)、最差和平均效率422.1.5分析框架概要算法的時(shí)間效率和空間效率都用輸入規(guī)模的函數(shù)進(jìn)行度量。我們用算法基本操作的執(zhí)行次數(shù)來度量算時(shí)間效率。通過計(jì)算算法消耗的額外存儲(chǔ)單元的數(shù)量來度量空間效率。在輸入規(guī)模相同的情況下，有些算法的效率會(huì)的顯著差異。對(duì)于這樣的算法，我們需要區(qū)分最差效率，平均效率和最優(yōu)效率。本框架主要關(guān)心，當(dāng)算法的輸入規(guī)模趨向于無限大的時(shí)候，其運(yùn)行時(shí)間（消耗的額外空間）函數(shù)的增長(zhǎng)次數(shù)。2.1.5分析框架概要432.2漸進(jìn)符號(hào)和基本效率類型2.2.1非正式的介紹非正式來說，O(g(n))是增長(zhǎng)次數(shù)小于等于是g(n)(以及其常數(shù)倍，n趨向于無窮大)的函數(shù)集合。n∈O(n2),100n+5∈O(n2),1/2(n(n-1))∈O(n2),n3∈/O(n2),第二個(gè)符號(hào)?(g(n))，代表增長(zhǎng)次數(shù)大于等于g(n)(以及其常數(shù)倍,n趨向于無窮大)的函數(shù)集合。

n3∈?(n2)，1/2(n(n-1))∈?(n2)，但是100n+5∈/?(n2)最后，Θ(g(n))是增長(zhǎng)次數(shù)等于g(n))(以及其常數(shù)倍,n趨向于無窮大)的函數(shù)集合。因些，每一個(gè)二次方程an2+bn+c在a>0的情況下都包含在Θ(n2)中，除了無數(shù)類似于n2+sinn和n2+logn的函數(shù)（你能解釋原因嗎？）。2.2漸進(jìn)符號(hào)和基本效率類型2.2.1非正式的介紹442.2.2符號(hào)О

定義1我們把函數(shù)t(n)屬于O(g(n))，記作t(n)∈

O(g(n));它的成立條件是：對(duì)于所有足夠大的n，t(n)的上界由g(n)的常數(shù)倍數(shù)所確定，也就是說，存在大于0的常數(shù)c和非負(fù)的整數(shù)n0，使得：對(duì)于所有的n≥n0來說，t(n)≤cg(n)n0之前的情況無關(guān)重要cg(n)t(n)n符號(hào)O：t(n)∈O(g(n))n02.2.2符號(hào)Оn0之前的情況無關(guān)重要cg(n)t(n)n452.2.3符號(hào)?定義2我們把函數(shù)t(n)屬于?(g(n))，記作t(n)∈?(g(n))，它的成立條件是：對(duì)于所有足夠大的n，t(n)的下界由g(n)的常數(shù)倍所確定，也就是說，存在大于0的常數(shù)c和非負(fù)的整數(shù)n0，使得：對(duì)于所有的n≥n0來說，t(n)≥cg(n)n0之前的情況無關(guān)重要cg(n)t(n)n符號(hào)?：t(n)∈?(g(n))n02.2.3符號(hào)?n0之前的情況無關(guān)重要cg(n)t(n)n462.2.4符號(hào)Θ定義3我們把函數(shù)t(n)屬于Θ(g(n))，記作t(n)∈Θ(g(n));它的成立條件是：對(duì)于所有足夠大的n，t(n)的上界和下界都由g(n)的常數(shù)倍數(shù)所確定，也就是說，存在大于0的常數(shù)c1，c2和和非負(fù)的整數(shù)n0，使得：對(duì)于所有的n≥n0來說，c2g(n)≤t(n)≤c1g(n)n0之前的情況無關(guān)重要c1g(n)t(n)n符號(hào)Θ：t(n)∈Θ(g(n))n0c2g(n)2.2.4符號(hào)Θn0之前的情況無關(guān)重要c1g(n)t(n472.2.5漸進(jìn)符號(hào)的有用特性定理如果t1(n)∈O(g1(n))并且t2(n)∈O(g2(n))，則t1(n)+t2(n)∈O(max{g1(n),g2(n)})(對(duì)于?和Θ符號(hào)，類似的斷言也為真)對(duì)于兩個(gè)連續(xù)執(zhí)行部分組成的算法，應(yīng)該如何應(yīng)用這個(gè)特性呢？它意味著該算法的整體效率是由具有較大的增長(zhǎng)次數(shù)的部分所決定的，即它的效率較差的部分.2.2.5漸進(jìn)符號(hào)的有用特性482.2.6利用極限比較增長(zhǎng)次數(shù)雖然符號(hào)O，?和Θ的正式定義對(duì)于證明它們的抽象性質(zhì)是不可缺少的，但我們很小直接用它們來比較兩個(gè)特定函數(shù)的增長(zhǎng)次數(shù)。有一種較為簡(jiǎn)便的比較方法，它是基于對(duì)所計(jì)論的兩個(gè)函數(shù)的比率求極限。有3種極限情況會(huì)發(fā)生：2.2.6利用極限比較增長(zhǎng)次數(shù)492.2.7基本的效率類型

1constantlognlogarithmicnlinearnlognnlognn2quadraticn3cubic2nexponentialn!factorial2.2.7基本的效率類型1constantlognloga50練習(xí)Problem2,4.b,5,and6.aP48練習(xí)Problem2,4.b,5,and6.a512.3非遞歸算法的數(shù)學(xué)分析例1考慮一下從n個(gè)元素的列表中查找元素最大值的問題.簡(jiǎn)單起見,我們假設(shè)列表是用數(shù)組實(shí)現(xiàn)的。下面給出一個(gè)解決問題的標(biāo)準(zhǔn)算法的偽代碼。算法MaxElement(A[0..n-1])

//求給定數(shù)組中最大元素的值//輸入：實(shí)數(shù)數(shù)組A[0..n-1]//輸出：A中最大元素的值maxval←A[0]fori←1ton-1doifA[i]>maxvalmaxval←A[i]returnmaxval2.3非遞歸算法的數(shù)學(xué)分析例1考慮一下從n個(gè)元素的列表中查52如何確定基本操作呢？由于做每一次循環(huán)都會(huì)進(jìn)行一次比較，所以把比較作為基本操作如何確定基本操作呢？53我們把C(n)記作比較運(yùn)算的執(zhí)行次數(shù),并試圖尋找一個(gè)公式將它表達(dá)為規(guī)模n的函數(shù)。由于該算法每執(zhí)行一次循環(huán)就會(huì)做一次比較，并且對(duì)于循環(huán)變量i在1和n-1(包含在內(nèi))中的每個(gè)值都會(huì)做一次循環(huán)，所以，我們得到C(n)的下列求和表達(dá)式：

我們把C(n)記作比較運(yùn)算的執(zhí)行次數(shù),并試圖尋找一個(gè)54分析非遞歸算法效率的通用方案1.決定用哪個(gè)(哪些)參數(shù)作為輸入規(guī)模的度量2.找出算法的基本操作（作為一規(guī)律，它總是位于算法的最內(nèi)層循環(huán)中）。檢查基本操作的執(zhí)行次數(shù)是否只依賴輸入規(guī)模。如果它還依賴一些其他的特性，則最差效率、平均效率以及最優(yōu)效率（如果必要）需要分別研究。建立一個(gè)算法基本操作執(zhí)行次數(shù)的求和表達(dá)式。利用求和運(yùn)算的標(biāo)公式和法則來建立一個(gè)操作次數(shù)的閉合公式，或者至少確定它的增長(zhǎng)次數(shù)。分析非遞歸算法效率的通用方案1.決定用哪個(gè)(哪些)參55例2考慮一下元素惟一性問題：驗(yàn)證給定數(shù)組中的元素是否全部惟一。下面這個(gè)簡(jiǎn)單直接的算法可以解決該問題。算法UniqueElements(A[0..n-1])//驗(yàn)證給定數(shù)組中的無素是否全部惟一//輸入：數(shù)組A[0..n-1]//輸出：如果A中的元素全部惟一，返回“true”//否則，返回“false”.fori←1ton-2doforj←i+1ton-1doifA[i]=A[j]returnfalseReturntrue例2考慮一下元素惟一性問題：驗(yàn)證給定數(shù)組中的元素是否全部惟56基本操作：比較除了和n有關(guān)外，還取決于數(shù)組中是否有相同的元素，以及它們?cè)跀?shù)組中的位置必須研究其最優(yōu)，平均和最差效率基本操作：比較57這個(gè)結(jié)果是完全可以預(yù)測(cè)的：在最壞的情況下，對(duì)于n個(gè)元素的所有n(n-1)/2對(duì)兩兩組合，該算法都要比較一遍。這個(gè)結(jié)果是完全可以預(yù)測(cè)的：在最壞的情況下，對(duì)于n個(gè)元素的所有58矩陣乘法Algorithm

MatrixMultiplication(A[0..n-1,0..n-1],B[0..n-1,0..n-1])//Multipliestwosquarematricesofordernbythedefinition-basedalgorithm//Input:twon-by-nmatricesAandB//Output:MatrixC=ABfori0ton-1do forj0ton–1do C[i,j]0.0 fork0ton–1do C[i,j]C[i,j]+A[i,k]*B[k,j]returnC矩陣乘法AlgorithmMatrixMultiplica59乘法次數(shù)乘法次數(shù)602.4遞歸算法的數(shù)學(xué)分析例1對(duì)于任意非負(fù)整數(shù)n,計(jì)算階乘函數(shù)F(n)=n!的值。因?yàn)楫?dāng)n≥1時(shí)，n!=1·…·(n-1)·n=(n-1)!·n并且根據(jù)定義，0!=1，我們可以使用下面的遞歸算法計(jì)算F(n)=F(n-1)·n2.4遞歸算法的數(shù)學(xué)分析例1對(duì)于任意非負(fù)整數(shù)n,計(jì)算階乘61算法F(n)

//遞歸計(jì)算n!//輸入：非負(fù)整數(shù)n//輸出：n!的值ifn=0return1elsereturnF(n-1)*n我們用n本身來指出算法的輸入規(guī)模（而不是它的二進(jìn)制表示的比特?cái)?shù)）。該算法的基本操作是乘法，我們把它的執(zhí)行次數(shù)記作M(n)。算法設(shè)計(jì)與分析基礎(chǔ)第2版算法分析第2章-課件62因?yàn)楹瘮?shù)F(n)的計(jì)算是根據(jù)下面公式：當(dāng)n>0時(shí)，F(xiàn)(n)=F(n-1)*n所以，計(jì)算這個(gè)公式時(shí)，用到的乘法數(shù)量M(n)需要滿足這個(gè)等式：當(dāng)n>0時(shí)，M(n)=M(n-1)+1的確，計(jì)算F(n-1)需要用M(n-1)次乘法，還有一次乘法用來把該結(jié)果乘法n。為了確定一個(gè)惟一解，我們還需要一初始條件來告訴我們?cè)撔蛄械钠鹗贾?。因?yàn)楹瘮?shù)F(n)的計(jì)算是根據(jù)下面公式：63為了得到這個(gè)起始值，我們可以觀察該算法停止遞歸調(diào)歸調(diào)用時(shí)的條件：ifn=0return1所以，我們所遵循的初始條件是：M(0)=0這樣，我們成功地建立了關(guān)于該算法的乘法次數(shù)M(n)的遞推關(guān)系和初始條件：當(dāng)n>0時(shí)，M(n)=M(n-1)+1M(0)=0最終結(jié)果為M(n)=M(n-1)+1=…=M(n-i)+i=…=M(n-n)+n=n