算法分析的基本概念和方法

第1章算法分析的基本概念和方法

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第1頁!內(nèi)容提要

一、算法及其特性

二、算法的時(shí)間空間復(fù)雜度

三、算法分析(AlgorithmAnalysis) 1.分析算法時(shí)間復(fù)雜度的基本步驟 2.算法時(shí)間復(fù)雜度的有關(guān)概念 3.分析、求解算法復(fù)雜度的方法

四、最優(yōu)算法(optimalalgorithm)算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第2頁!知識(shí)要點(diǎn)

算法分析的概念復(fù)雜度漸近表示的記號(hào)：O,,

平均時(shí)間復(fù)雜度，最壞時(shí)間復(fù)雜度，最好時(shí)間復(fù)雜度最優(yōu)算法分析算法復(fù)雜度的基本方法分析算法時(shí)間復(fù)雜度的步驟基本運(yùn)算執(zhí)行頻數(shù)的統(tǒng)計(jì)方法數(shù)學(xué)知識(shí)：求和公式、定積分近似求和、遞歸方程的求解算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第3頁!學(xué)習(xí)要求

掌握算法復(fù)雜度的基本概念熟悉算法復(fù)雜度分析的基本方法算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第4頁!1.1．算法及其特性衡量算法性能一般有下面幾個(gè)標(biāo)準(zhǔn)：確定性易讀性健壯性算法的時(shí)間和空間性能：高效率和低存儲(chǔ)空間

本課程中主要討論算法的時(shí)間和空間性能，并以此作為衡量算法性能的重要標(biāo)準(zhǔn)，而且主要側(cè)重于時(shí)間方面。

三、衡量算法性能的標(biāo)準(zhǔn)算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第5頁!1.2.算法的時(shí)間空間復(fù)雜度算法的空間復(fù)雜度：在算法運(yùn)行期間所需要的內(nèi)存空間，通常指除開容納輸入數(shù)據(jù)之外的附加空間（auxiliaryspace,orworkspace）。通常用漸進(jìn)形式表示。比如，S(n)=O(n2)、(n2)或(n2)二、算法的空間復(fù)雜度(SpaceComplexity)

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第6頁!1.3.分析復(fù)雜度的基本步驟

對(duì)算法的分析必須脫離具體的計(jì)算機(jī)結(jié)構(gòu)和程序設(shè)計(jì)語言。因此，比較兩個(gè)算法的好壞，看其中所需的運(yùn)算時(shí)間的長短是由算法所需的運(yùn)算次數(shù)決定的。任何一個(gè)算法都可能有幾種運(yùn)算，因此，我們抓住其中影響算法運(yùn)行時(shí)間最大的運(yùn)算作為基本運(yùn)算。如在一個(gè)字表中尋找Z的問題，把Z和表中元素的比較作為基本運(yùn)算。兩個(gè)實(shí)數(shù)矩陣相乘的問題中，則把兩個(gè)實(shí)數(shù)相乘作為基本運(yùn)算。

一、選取一種運(yùn)算作為基本運(yùn)算(basicoperation)

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第7頁!1.3.分析復(fù)雜度的基本步驟

同一個(gè)問題對(duì)不同的輸入，基本運(yùn)算的次數(shù)亦可能不同。因此，我們引進(jìn)問題大?。匆?guī)模，size）的概念。例如，在一個(gè)姓名表中尋找給定的Z的問題，問題的大小可用表中姓名的數(shù)目表示。對(duì)于兩個(gè)實(shí)數(shù)矩陣相乘的問題，其大小可用矩陣的階來表示。而對(duì)于遍歷一棵二叉樹的問題，其大小是用樹中結(jié)點(diǎn)數(shù)來表示等等。這樣，一個(gè)算法的基本運(yùn)算的次數(shù)就可用問題的大小n的函數(shù)f(n)來表示。

二、表示出在算法運(yùn)行期間基本運(yùn)算執(zhí)行的總頻數(shù)算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第8頁!1.3.分析復(fù)雜度的基本步驟 在實(shí)際中精確地求一個(gè)算法的基本運(yùn)算次數(shù)f(n)等于多少，往往不容易，甚至有時(shí)根本不可能，有些即使求出結(jié)果很長，很繁瑣，不易比較，需要簡化。這時(shí)候我們可以不精確地估計(jì)f(n)。此外，我們分析算法的時(shí)間目的主要在于，能區(qū)分不同算法的優(yōu)劣，在n很小時(shí)候，差別不大，隨著n的逐漸增大，差別越來越大，是個(gè)極限行為?；谏鲜鲈颍M(jìn)下面漸近表示的方法。復(fù)雜度漸近表示可以將簡潔地表示出復(fù)雜度的數(shù)量級(jí)別。

三、漸近時(shí)間復(fù)雜度(asymptotictimeplexity)

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第9頁!1.3.分析復(fù)雜度的基本步驟設(shè)f(n)和g(n)均是從自然數(shù)集到非負(fù)實(shí)數(shù)集上的函數(shù)。如果存在常數(shù)c>0和一個(gè)自然數(shù)n0，使得對(duì)于任意的n≥n0，均有

f(n)≥cg(n),則，f(n)=(g(n))。

含義：階至少為g(n)的函數(shù)，即下限。讀法：(g(n))讀作“omegag(n)”。

2.-記號(hào)算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第10頁!1.3.分析復(fù)雜度的基本步驟[例1]設(shè)f(n)=10n2+20n。則有

f(n)=O(n2)

f(n)=(n2)

f(n)=(n2)

[例2]

設(shè)f(n)=aknk+ak-1nk-1+…+a1n+a0,(ak>0)。則有

f(n)=O(nk)

f(n)=(nk)

f(n)=(nk)四、舉例算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第11頁!1.3.分析復(fù)雜度的基本步驟各種復(fù)雜度比較示意圖如下。

五、復(fù)雜度比較示意圖

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第12頁!1.4.復(fù)雜度的有關(guān)概念

一、算法時(shí)間復(fù)雜度

對(duì)于算法的時(shí)間復(fù)雜度，通常從分平均、最壞、最好幾種情形來衡量，尤其是前兩種。算法的平均復(fù)雜性

設(shè)Dn是對(duì)于所考慮問題來說大小為n的輸入的集合，并設(shè)i是Dn的一個(gè)元素，p(i)是i出現(xiàn)的概率，t(i)是算法在輸入i時(shí)所執(zhí)行的基本運(yùn)算次數(shù)。那么，算法的平均復(fù)雜性定義為：

A(n)=

i∈Dnp(i)t(i)

算法的最壞復(fù)雜性

W(n)=MAXi∈Dnt(i)

算法的最好復(fù)雜性

B(n)=MINi∈Dnt(i)

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第13頁!算法分析方法例：順序搜索算法template<classType>intseqSearch(Type*a,intn,Typek){for(inti=0;i<n;i++) if(a[i]==k)returni;return-1;}算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第14頁!算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第15頁!算法分析的基本法則非遞歸算法：（1）for/while循環(huán)循環(huán)體內(nèi)計(jì)算時(shí)間*循環(huán)次數(shù)；（2）嵌套循環(huán)循環(huán)體內(nèi)計(jì)算時(shí)間*所有循環(huán)次數(shù)；（3）順序語句各語句計(jì)算時(shí)間相加；（4）if-else語句if語句計(jì)算時(shí)間和else語句計(jì)算時(shí)間的較大者。算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第16頁!在最好情況下，ti=1,for1

i<n;在最壞情況下，ti

i+1,for1

i<n;算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第17頁!1.5.分析和求解復(fù)雜度的方法根據(jù)循環(huán)來統(tǒng)計(jì)基本操作的次數(shù)利用遞歸關(guān)系來表示基本操作的次數(shù)用平攤的辦法來統(tǒng)計(jì)基本操作的次數(shù)(AmortizedAnalysis)一、統(tǒng)計(jì)算法基本運(yùn)算的基本方法

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第18頁!1.5.分析和求解復(fù)雜度的方法[例2]利用遞歸關(guān)系來求基本操作的次數(shù)

求Fibonacci數(shù)列的第n項(xiàng)。該數(shù)列的定義為：

F0=F1=1,Fi=Fi-1+Fi-2，i

2。

由這一數(shù)學(xué)定義自然地導(dǎo)出一個(gè)遞歸算法。int

F(int

n){ if(n==0||n==1)return1;

else

if(n>=2)return

F(n-1)+F(n-2);}解：該算法的計(jì)算時(shí)間T(n)滿足遞歸方程：T(n)=T(n-1)+T(n-2)+1,n>1；初始條件T(0)=T(1)=0。

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第19頁!解：算法的基本操作為元素的插入和刪除操作。算法中插入操作的次數(shù)為n次，而刪除操作的次數(shù)最多為n-1次，所以，算法的基本操作最少n次，最多2n-1次。算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第20頁!1.5.分析和求解復(fù)雜度的方法

2.

積分近似求和

如果連續(xù)函數(shù)f(n)是單調(diào)遞減的，則有

如果連續(xù)函數(shù)f(n)是單調(diào)遞增的，則有

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第21頁!1.5.分析和求解復(fù)雜度的方法算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第22頁!1.5.分析和求解復(fù)雜度的方法 遞歸是一種重要的程序設(shè)計(jì)方法。有些問題的算法運(yùn)用遞歸過程來表示不僅自然簡潔，而且也易于驗(yàn)證其正確性。遞歸算法的特點(diǎn)就是：易讀，易寫，易證。遞歸和歸納緊密相關(guān)。歸納定義的東西往往易寫出其遞歸的算法；而遞歸的算法往往可用歸納法來證明。遞歸算法的時(shí)間復(fù)雜度分析往往需要借助于求解遞歸方程或者遞歸不等式的解得到。 遞歸方程的類型較多，涉及到的數(shù)學(xué)知識(shí)也較多。這里我們僅簡單地介紹分析算法復(fù)雜度時(shí)常見的幾類簡單遞歸方程的求法。三、遞歸關(guān)系算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第23頁!1.5.分析和求解復(fù)雜度的方法（1）線性非齊次遞歸方程

主要解法：差分方程法、數(shù)學(xué)歸納法等。算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第24頁!1.5.分析和求解復(fù)雜度的方法算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第25頁!1.6.最優(yōu)算法(optimalalgorithm)

如果能夠證明求解問題P的任何算法的時(shí)間是

(f(n)),那么稱求解問題P的時(shí)間為

O(f(n))的任一算法為問題P的最優(yōu)算法。一、最優(yōu)算法算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第26頁!1.1．算法及其特性

一、算法(algorithm)

算法就是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問題的一系列運(yùn)算。二、算法的五個(gè)特性確定性能行性有窮性輸入輸出算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第27頁!1.2.算法的時(shí)間空間復(fù)雜度

算法的時(shí)間復(fù)雜度：在算法運(yùn)行期間所花費(fèi)的時(shí)間。通常用漸進(jìn)形式表示。比如，T(n)=O(n2)、(n2)或(n2)一、算法的時(shí)間復(fù)雜度(TimeComplexity)算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第28頁!1.2.算法的時(shí)間空間復(fù)雜度

算法分析是指對(duì)于計(jì)算機(jī)算法的時(shí)間和空間復(fù)雜度進(jìn)行定量的分析。為了確切起見，假定執(zhí)行算法的計(jì)算機(jī)是滿足如下條件的“通用型”計(jì)算機(jī)：順序處理機(jī)：每次執(zhí)行程序中的一條指令；RAM足夠大；在固定的時(shí)間內(nèi)可把一個(gè)數(shù)從一個(gè)單元取出或者存入。

下面將學(xué)習(xí)算法分析的主要內(nèi)容：分析算法時(shí)間復(fù)雜度的基本步驟算法時(shí)間復(fù)雜度的有關(guān)概念分析、求解算法復(fù)雜度的數(shù)學(xué)知識(shí)三、算法分析(AlgorithmAnalysis)

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第29頁!1.3.分析復(fù)雜度的基本步驟一個(gè)計(jì)算步驟，如果其時(shí)間耗費(fèi)總是不超過某個(gè)常量，而與輸入和算法無關(guān)，則稱之為元運(yùn)算。

元運(yùn)算(elementaryoperation)

常見的元運(yùn)算

算術(shù)運(yùn)算：加、減、乘、除；比較和邏輯運(yùn)算；賦值運(yùn)算，包括指針賦值（比如，在遍歷表或樹時(shí)的指針賦值）；等等。

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第30頁!1.3.分析復(fù)雜度的基本步驟

在一個(gè)算法中，出現(xiàn)的頻數(shù)最高（在相差一個(gè)常數(shù)因子的意義上）的元運(yùn)算稱為基本元算。

基本運(yùn)算(basicoperation)

常見的基本運(yùn)算

當(dāng)分析查找和排序的算法時(shí)，如果元素的比較是元運(yùn)算，則可作為基本運(yùn)算；在矩陣乘法的算法中，數(shù)的乘法可作為基本運(yùn)算；當(dāng)遍歷鏈表時(shí)，給指針賦值或者更新指針的操作可作為基本運(yùn)算；在圖的遍歷中，可以將訪問節(jié)點(diǎn)的操作為基本運(yùn)算；等等。算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第31頁!1.3.分析復(fù)雜度的基本步驟設(shè)f(n)和g(n)均是從自然數(shù)集到非負(fù)實(shí)數(shù)集上的函數(shù)。如果存在常數(shù)c>0和一個(gè)自然數(shù)n0，使得對(duì)于任意的n≥n0，均有

f(n)≤cg(n),則f(n)=O(g(n))。含義：階至多為g(n)的函數(shù)，即上限。讀法：O(g(n))讀作“大Ohg(n)”。1.O-記號(hào)

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第32頁!1.3.分析復(fù)雜度的基本步驟設(shè)f(n)和g(n)均是從自然數(shù)集到非負(fù)實(shí)數(shù)集上的函數(shù)。如果存在一個(gè)自然數(shù)n0和兩個(gè)正常數(shù)c1，c2，使得對(duì)于任意的n≥n0，均有

c1g(n)≤f(n)≤c2g(n),則，f(n)=(g(n))。含義：階恰好為g(n)的函數(shù)。讀法：(g(n))讀作“thetag(n)”。

3.-記號(hào)算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第33頁!1.3.分析復(fù)雜度的基本步驟[例3]設(shè)f(n)=2n，g(n)=n!。則有

f(n)=O(g(n))

但是，f(n)(g(n))

因此，f(n)

(g(n))此時(shí)，記作O(f(n))<O(g(n))。

四、舉例算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第34頁!1.3.分析復(fù)雜度的基本步驟各種復(fù)雜度比較示意圖如下。

五、復(fù)雜度比較示意圖

算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第35頁!1.4.復(fù)雜度的有關(guān)概念[例1]檢索問題的順序查找算法1.1。

以元素的比較作為基本操作。考慮成功檢索的情況。最好情況下的時(shí)間復(fù)雜度：(1)最壞情況下的時(shí)間復(fù)雜度：(n)在等概率前提下，平均情況下的時(shí)間復(fù)雜度：(n)二、舉例算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第36頁!（1）Tmax(n)=max{T(i)|size(i)=n}=O(n)（2）Tmin(n)=min{T(i)|size(i)=n}=O(1)（3）在平均情況下，假設(shè)：(a)搜索成功的概率為p(0

p

1)；(b)在數(shù)組的每個(gè)位置i(0i<n)搜索成功的概率相同，均為p/n。算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第37頁!1.4.復(fù)雜度的有關(guān)概念[例2]直接插入排序算法1.5。

以元素的比較作為基本操作。最好情況下的時(shí)間復(fù)雜度：(n)最壞情況下的時(shí)間復(fù)雜度：在等概率前提下，平均情況下的時(shí)間復(fù)雜度：二、舉例算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第38頁!template<classType>voidinsertion_sort(Type*a,intn){Typekey;//costtimesfor(inti=1;i<n;i++){//c1n

key=a[i];//c2n-1

intj=i-1;//c3n-1

while(j>=0&&a[j]>key){//c4sumofti a[j+1]=a[j];//c5sumof(ti-1)

j--;//c6sumog(ti-1) }a[j+1]=key;//c7n-1

}}算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第39頁!對(duì)于輸入數(shù)據(jù)a[i]=n-i,i=0,1,…,n-1，算法insertion_sort達(dá)到其最壞情形。因此，由此可見，Tmax(n)=(n2)算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第40頁!1.5.分析和求解復(fù)雜度的方法[例1]根據(jù)循環(huán)來統(tǒng)計(jì)基本操作的次數(shù) Input:

n=（k為某個(gè)正整數(shù)）.

Output:count（step4的執(zhí)行次數(shù)）

1.count←0

2.while

n≥1

3.for

j←1ton

4.count←count+1

5.end

for

6.n←n/2

7.end

while

8.returncount解：基本操作的次數(shù)為算法分析的基本概念和方法共49頁，您現(xiàn)在瀏覽的是第41頁!1.5.分析和求解復(fù)雜度的方法[例3]

用平攤的辦法來統(tǒng)計(jì)基本操作的