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

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

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

IntroductiontoAlgorithms(SecondEdition),

TheMITPress,2013.

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

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

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

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

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

例如:

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

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

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

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

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

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

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

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

一般地，一些關(guān)鍵操作執(zhí)行的次數(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)算法時間復(fù)雜性估計：∵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ù)雜性估計：

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

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

例子:

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

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

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

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

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

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

漸近意義下的記號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三點注意事項：（1）用來作比較的函數(shù)g(n)應(yīng)該盡量接近所考慮的函數(shù)f(n)。

如：3n+2=O(n2)

松散的界限；

3n+2=O(n)

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

如:

n2+100n+6

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

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

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

n2+100n+6>C×n。

同理，3n2+4×2n=O(n2)是錯誤的界限。（3）f(n)=O(g(n))不能寫成g(n)=O(f(n))。因為兩者并不等價。21漸近記號

的定義：

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

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

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

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

，有f(n)≥C(g(n))。此時，稱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

}算法時間復(fù)雜性估計：

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

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

(1)

，因此在最壞情況下，總的時間復(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）這個方法為估計形如

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

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

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

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

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

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

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

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

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

＝nlog39＝n2

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

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

＝nlog3/21＝n0=1

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

。27