計(jì)算機(jī)算法設(shè)計(jì)與分析第一章

1計(jì)算機(jī)算法設(shè)計(jì)與分析主講教師：金英TheDesignandAnalysisofComputerAlgorithms2【參考教材】

王曉東,計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版),電子工業(yè)出版社，2012。ThomasH.Cormen,CharlesE.Leiserson,andRonaldL.Rivest.

IntroductiontoAlgorithms(SecondEdition),

TheMITPress,2013.

[算法導(dǎo)論（第三版）]【課程基礎(chǔ)】本課程要求學(xué)生在學(xué)習(xí)之前已經(jīng)熟練掌握C/C++程序設(shè)計(jì)，學(xué)習(xí)過高等數(shù)學(xué)、線性代數(shù)、離散數(shù)學(xué)、概率論與數(shù)理統(tǒng)計(jì)、數(shù)據(jù)結(jié)構(gòu)等課程。3【主要教學(xué)內(nèi)容】設(shè)計(jì)算法及分析算法的理論、方法和技術(shù)；可計(jì)算問題的算法設(shè)計(jì)與分析。分為下述部分介紹：算法概述遞歸與分治策略動(dòng)態(tài)規(guī)劃貪心算法回溯法分支限界法4第一章：算法概述570年代前計(jì)算機(jī)科學(xué)基礎(chǔ)的主題沒有被清楚地認(rèn)清70年代Knuth出版了《TheArtofComputerProgramming》以算法研究為主線確立了算法為計(jì)算機(jī)科學(xué)基礎(chǔ)的重要主題1974年獲得圖靈獎(jiǎng)70年代后算法作為計(jì)算機(jī)科學(xué)核心推動(dòng)了計(jì)算機(jī)科學(xué)技術(shù)飛速發(fā)展算法是計(jì)算機(jī)科學(xué)的重要主題

第一節(jié)算法在計(jì)算機(jī)科學(xué)中的地位6算法設(shè)計(jì)與分析可計(jì)算理論計(jì)算復(fù)雜性理論計(jì)算機(jī)科學(xué)技術(shù)的體系解決一個(gè)計(jì)算問題的過程可計(jì)算否能行可計(jì)算否軟件系統(tǒng)用計(jì)算機(jī)語言實(shí)現(xiàn)算法設(shè)計(jì)與分析算法數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)編譯、OS、…7可計(jì)算理論計(jì)算模型可計(jì)算問題/不可計(jì)算問題計(jì)算模型的等價(jià)性--圖靈/Church命題計(jì)算復(fù)雜性理論在給定的計(jì)算模型下研究問題的復(fù)雜性固有復(fù)雜性復(fù)雜性下界平均復(fù)雜性復(fù)雜性問題的分類:P=NP?公理復(fù)雜性理論8算法設(shè)計(jì)和分析設(shè)計(jì)算法的理論、方法和技術(shù)分析算法的理論、方法和技術(shù)計(jì)算機(jī)軟件系統(tǒng)軟件工具軟件應(yīng)用軟件9

第二節(jié)算法與程序算法（Algorithm）的概念通俗地講

算法是指解決問題的一種方法或一個(gè)過程。嚴(yán)格地講

算法是由若干條指令組成的有窮序列,且滿足下述性質(zhì)：（1）輸入:有零個(gè)或多個(gè)由外部提供的量作為算法的輸入。（2）輸出:算法產(chǎn)生至少一個(gè)量作為輸出。（3）確定性:組成算法的每條指令是清晰的，無歧義的。（4）有限性:算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。10算法與程序的區(qū)別程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)；程序可以不滿足算法的性質(zhì)（4）----有限性。

例如:

操作系統(tǒng)，它是一個(gè)在無限循環(huán)中執(zhí)行的程序，因而不是算法?？砂巡僮飨到y(tǒng)的各種任務(wù)看成是一些單獨(dú)的問題，每個(gè)問題由操作系統(tǒng)中的一個(gè)子程序通過特定的算法來實(shí)現(xiàn)。算法描述描述算法可以有多種形式。本課程將用C/C++語言或偽代碼描述算法。11算法復(fù)雜性的含義

一個(gè)算法的復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需的計(jì)算機(jī)資源（主要指時(shí)間和空間資源）的多少上。

第三節(jié)算法復(fù)雜性分析

算法的復(fù)雜性主要分為:

時(shí)間復(fù)雜性空間復(fù)雜性算法的復(fù)雜性分析的用處途:

為求解一個(gè)問題選擇最佳算法、最佳設(shè)備12隨著計(jì)算機(jī)要解決的問題越來越復(fù)雜，規(guī)模越來越大，對求解這類問題的算法作復(fù)雜性分析具有特別重要的意義。隨著計(jì)算機(jī)技術(shù)的迅速發(fā)展，對空間的要求往往不如對時(shí)間的要求那樣強(qiáng)烈。因此我們這里的分析主要強(qiáng)調(diào)時(shí)間復(fù)雜性的分析?？紤]時(shí)間復(fù)雜性的理由：某些用戶需要提供程序運(yùn)行時(shí)間的上限（用戶可接受的）；所開發(fā)的程序需要提供一個(gè)滿意的實(shí)時(shí)反應(yīng)。13本課程考慮如下三種情況下的時(shí)間復(fù)雜度：

最壞情況；最好情況；平均情況。時(shí)間復(fù)雜性的計(jì)算方法(即估算運(yùn)行時(shí)間的方法)

加、減、乘、除、比較、賦值等操作，一般被看作是基本操作，并約定所用的時(shí)間都是一個(gè)單位時(shí)間；通過計(jì)算這些操作分別執(zhí)行了多少次來確定程序總的執(zhí)行步數(shù)。

一般地，一些關(guān)鍵操作執(zhí)行的次數(shù)決定了算法的時(shí)間復(fù)雜度。14例1：二分查找算法intbsearch(K,L,H){if(H<L)return(-1);else{mid=(L+H)/2;

element=A[mid];if(element==K)return(mid)；

elseif（A[mid]>K）

return(bsearch(K,L,mid-1));elsereturn(bsearch(K,mid+1,H));}2321123+T(n/2)3+T(n/2)算法時(shí)間復(fù)雜性估計(jì)：∵T(n)=2當(dāng)n=0∵T(n)=11+T(n/2)當(dāng)n≥1

∴T(n)=O(logn)15例2：尋找最大元素template<classT>intMax(Ta[],intn){//尋找a[0:n-1]中的最大元素

intpos=0;for(inti=1;i<n;i++)if(a[pos]<a[i])pos=i;returnpos;}算法復(fù)雜性估計(jì)：

T(n)=O(n)16漸近復(fù)雜性分析

確定程序的操作計(jì)數(shù)和執(zhí)行步數(shù)的目的是為了比較兩個(gè)完成同一功能的程序的時(shí)間復(fù)雜性，預(yù)測程序的運(yùn)行時(shí)間隨著問題規(guī)模變化的變化量。

例子:

T(n)=3n2+4nlogn+7=3n2

進(jìn)一步分析可知，漸近復(fù)雜性分析只要關(guān)心的階就夠了，不必關(guān)心包含在中的常數(shù)因子。所以，我們還可對的分析進(jìn)一步簡化。

設(shè)T(n)是算法A的時(shí)間復(fù)雜性函數(shù)是算法A當(dāng)n→∞時(shí)的漸近時(shí)間復(fù)雜性，是T(n)中略去低階項(xiàng)所留下的主項(xiàng)。=n217常用的漸近函數(shù)

函數(shù)名稱函數(shù)名稱1常數(shù)n2平方logn對數(shù)n3立方n線性2n指數(shù)nlognn倍lognn！階乘綜上分析，我們已經(jīng)給出了簡化算法復(fù)雜性分析的方法和步驟，即只考慮當(dāng)問題的規(guī)模充分大時(shí)，算法復(fù)雜性在漸近意義下的階。為此引入漸近符號。在那之前，首先給出常用的漸近函數(shù)。18

在下面的討論中，用f(n)表示一個(gè)程序的時(shí)間或空間復(fù)雜性，它是問題規(guī)模n（一般是輸入規(guī)模）的函數(shù)。由于一個(gè)程序的時(shí)間或空間需求是一個(gè)非負(fù)的實(shí)數(shù)，我們假定函數(shù)f(n)對于n的所有取值均為非負(fù)實(shí)數(shù)，而且還可假定n≥0。漸近記號O的定義:

f(n)=O(g(n))當(dāng)且僅當(dāng)存在正的常數(shù)C和n0，使得對于所有的n≥n0，有f(n)≤Cg(n)。此時(shí)，稱g(n)是f(n)的一個(gè)上界。

漸近意義下的記號19例：100

=O(1):f(n)等于非零常數(shù)的情形。3n+2=O(n):

可取C＝4，n0＝2100n+6=O(n):

可取

C=101，n0＝610n2+4n+3=O(n2):

可取C=？,n0＝？6×2n+n2=O(2n):

可取C=7，n0=43×logn+2×n+n2=O(n2)n×logn+n2=O(n2)3n+2=O(n2)20三點(diǎn)注意事項(xiàng)：（1）用來作比較的函數(shù)g(n)應(yīng)該盡量接近所考慮的函數(shù)f(n)。

如：3n+2=O(n2)

松散的界限；

3n+2=O(n)

較好的界限。（2）不要產(chǎn)生錯(cuò)誤界限。

如:

n2+100n+6

當(dāng)n<3時(shí)，n2+100n+6<106n，

由此就認(rèn)為n2+100n+6＝O(n)是錯(cuò)誤的!

事實(shí)上，對任何正常數(shù)C，只要n>C-100就有

n2+100n+6>C×n。

同理，3n2+4×2n=O(n2)是錯(cuò)誤的界限。（3）f(n)=O(g(n))不能寫成g(n)=O(f(n))。因?yàn)閮烧卟⒉坏葍r(jià)。21漸近記號

的定義：

f(n)=Θ(g(n))當(dāng)且僅當(dāng)存在正常數(shù)和C1，C2和n0，使得對于所有的n≥n0,有C1(g(n))≤f(n)≤

C2(g(n))。此時(shí)，稱f(n)與g(n)同階。漸近記號的定義：

f(n)=Ω(g(n))

當(dāng)且僅當(dāng)存在正的常數(shù)C和n0，使得對于所有的n≥n0

，有f(n)≥C(g(n))。此時(shí)，稱g(n)是f(n)的下界。例：

3n+2=Θ(n)

10n2+4n+2=Θ(n2)

5×2n+n2=

Θ(2n)

22例3：非遞歸的折半搜索算法template<classT>intBinarySearch(Ta[],constT&x,intn){//在a[0]<=a[1]<=···<=a[n-1]中搜索x

//如果找到，則返回所在位置，否則返回–1intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle–1;}return–1;

//未找到x

}算法時(shí)間復(fù)雜性估計(jì)：

while的每次循環(huán)（最后一次除外）都將以減半的比例縮小搜索范圍，所以，該循環(huán)在最壞的情況下需要執(zhí)行(log(n))次。

由于每次循環(huán)需耗時(shí)

(1)

，因此在最壞情況下，總的時(shí)間復(fù)雜性為

(log(n))。23第四節(jié)遞歸方程解的漸近階的求法三種求遞歸方程解的漸近階的方法：

(1)代入法（SubstitutionMethod）

Guessfirst,然后用數(shù)學(xué)歸納法證明.(2)迭代法(IterationMethod)

循環(huán)地展開遞歸方程，把遞歸方程轉(zhuǎn)化為和式，然后可使用求和技術(shù)解之

(3)套用公式法（Mastermethod）求解型為T(n)=aT(n/b)+f(n)的遞歸方程24（3）套用公式法（Mastermethod）這個(gè)方法為估計(jì)形如

T(n)=aT(n/b)+f(n)的遞歸方程解的漸近階提供三個(gè)可套用的公式。注：上式是一個(gè)遞歸方程，其中：

a≥1和b>1是常數(shù)，

f(n)是一個(gè)確定的正函數(shù)。25

這里涉及的三類情況，都是用f(n)與nlogba作比較。定理直觀地告訴我們，遞歸方程解的漸近階由這兩個(gè)函數(shù)中的較大者決定。在第一類情況下，nlogba的階較大，

則T(n)=Θ(nlogba)。在第二類情況下，f(n)和nlogba同階，

則T(n)=Θ(nlogbalogn)。在第三類情況下，f(n)的階較大，

則T(n)=Θ(f(n))。

26例１：T(n)=9T(n/3)+n

此時(shí)，a=9,b=3,f(n)=n，∴nlogba

＝nlog39＝n2

可套用第一類情況得T(n)=Θ(n2)。例2：T(n)=T(2n/3)+1

此時(shí)，a=1,b=3/2,f(n)=1，∴nlogba

＝nlog3/21＝n0=1

可套用第二類情況得T(n)=Θ(logn)

。27