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

課程支配理論課：1～10周，40學(xué)時(shí)周二(5-6)、周五(1-2)上機(jī)：18學(xué)時(shí)期末考試：閉卷筆試，第11周上課點(diǎn)名三次不到者取消考試資格；遲到或作業(yè)缺交，一次扣10分（平常成果）。1教學(xué)目的和要求本課程是計(jì)算機(jī)類專業(yè)的專業(yè)基礎(chǔ)課程；通過(guò)課程學(xué)習(xí)和上機(jī)實(shí)踐，對(duì)計(jì)算機(jī)常用算法有一個(gè)較全面的了解，駕馭通用算法的一般設(shè)計(jì)方法；學(xué)會(huì)對(duì)算法的時(shí)間、空間困難度分析，駕馭提高算法效率的方法和途徑。2學(xué)習(xí)算法的重要性（一）從理論和實(shí)踐的角度理解—計(jì)算機(jī)科學(xué)的基石；駕馭標(biāo)準(zhǔn)算法（二）從算法對(duì)于程序的重要性來(lái)講—皮之不存，毛將附焉？（三）從對(duì)同學(xué)們的實(shí)力培育看—開(kāi)發(fā)分析問(wèn)題的實(shí)力3算法分析與設(shè)計(jì)課程

與數(shù)據(jù)結(jié)構(gòu)課程（一）數(shù)據(jù)結(jié)構(gòu)關(guān)切的對(duì)象各種數(shù)據(jù)結(jié)構(gòu)的作用和效率、具體的問(wèn)題（二）算法設(shè)計(jì)與分析關(guān)切的對(duì)象算法設(shè)計(jì)技術(shù)的適用性和效率、一般性方法4授課內(nèi)容第1章算法概述第2章遞歸與分治策略第3章動(dòng)態(tài)規(guī)劃第4章貪心算法第5章回溯法第6章分支限界法*7-9章屬探討生學(xué)習(xí)內(nèi)容，可自學(xué)了解。5第1章算法概述學(xué)習(xí)要點(diǎn):一、理解算法的概念，以及問(wèn)題求解的過(guò)程。二、駕馭算法的幾種描述方式。三、理解算法的計(jì)算困難性概念。四、駕馭算法漸近困難性的數(shù)學(xué)表述。6什么是算法？我們來(lái)編寫(xiě)一個(gè)燒開(kāi)水的算法：輸入自來(lái)水循環(huán)（反復(fù)）加熱直到水開(kāi)輸出開(kāi)水7一、算法(Algorithm)

算法概念：通俗地講，算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。嚴(yán)格地講，算法是由若干條指令組成的有窮序列。圖1.1算法的概念圖8（一）算法的性質(zhì)1、算法具有某些特性，如下幾條：(1)輸入：有零個(gè)或多個(gè)外部供應(yīng)的量作為算法的輸入。(2)輸出：算法產(chǎn)生至少一個(gè)量作為輸出。這些輸出是和輸入有某種特定關(guān)系的量。9（一）算法的性質(zhì)(3)確定性：組成算法的每條指令是清晰，無(wú)歧義的。(4)有限性（有窮性）：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。10（一）算法的性質(zhì)(5)可實(shí)現(xiàn)性：此性質(zhì)是指算法中有待實(shí)現(xiàn)的運(yùn)算都是相當(dāng)基本的，每種運(yùn)算至少在原理上能由人用紙和筆在有限的時(shí)間內(nèi)完成。（補(bǔ)充）11（一）算法性質(zhì)2、關(guān)于算法有幾個(gè)要點(diǎn)：(1)算法所處理的輸入的值域必需嚴(yán)格定義。(2)同樣一種算法可以用幾種不同的形式來(lái)描述。12（一）算法性質(zhì)(3)同一個(gè)問(wèn)題可以存在多種解決的算法。(4)同一個(gè)問(wèn)題的幾種算法可能會(huì)基于完全不同的解題思路，而且解題速度也會(huì)有顯著不同。13（二）問(wèn)題求解過(guò)程1)問(wèn)題的陳述用科學(xué)規(guī)范的語(yǔ)言,對(duì)所求解的問(wèn)題做精確的描述.2)建立數(shù)學(xué)模型通過(guò)對(duì)問(wèn)題的分析,找出其中的全部操作對(duì)象及操作對(duì)象之間的關(guān)系并用數(shù)學(xué)語(yǔ)言加以描述.3)算法設(shè)計(jì)依據(jù)數(shù)學(xué)模型設(shè)計(jì)問(wèn)題的計(jì)算機(jī)求解算法.14（二）問(wèn)題求解過(guò)程4)算法的正確性證明

證明算法對(duì)一切合法輸入均能在有限次計(jì)算后產(chǎn)生正確輸出.5)算法的程序?qū)崿F(xiàn)將算法正確地編寫(xiě)成機(jī)器語(yǔ)言程序.6)算法分析對(duì)執(zhí)行該算法所消耗的計(jì)算機(jī)資源進(jìn)行估算.15（三）如何設(shè)計(jì)算法通過(guò)學(xué)習(xí)已被實(shí)踐證明是有用的一些基本設(shè)計(jì)策略，如遞歸、回溯等，駕馭一般的算法設(shè)計(jì)方法，學(xué)會(huì)設(shè)計(jì)高效的算法。16（四）如何確認(rèn)算法（證明其正確性）證明算法對(duì)全部可能的輸入都能算出正確的答案，這一工作稱為算法確認(rèn)。這一領(lǐng)域是當(dāng)前很多計(jì)算機(jī)工作者集中探討的對(duì)象，還處于相當(dāng)時(shí)期的階段。在學(xué)習(xí)本課程中，我們僅對(duì)算法的正確性進(jìn)行一般的非形式化探討，以及對(duì)算法的程序?qū)崿F(xiàn)進(jìn)行測(cè)試驗(yàn)證。17（五）如何分析（評(píng)價(jià)）算法分析算法包括定量的分析算法須要多少計(jì)算時(shí)間和存儲(chǔ)空間，分析算法不僅可以預(yù)料算法能否有效得完成任務(wù)，而且可以知道算法在最壞、最好和平均狀況下的運(yùn)算時(shí)間，對(duì)解決同一問(wèn)題的不同算法的優(yōu)劣作出比較。18二、算法的幾種描述方式1、計(jì)算兩個(gè)整數(shù)的最大公約數(shù)問(wèn)題的一個(gè)現(xiàn)代數(shù)學(xué)術(shù)語(yǔ)表述歐幾里得算法基于的方法是重復(fù)應(yīng)用下列等式：

gcd(m,n)=gcd(n,mmodn)，直到mmodn等于0。gcd(60,24)=gcd(24,12)=gcd(12,0)=12注：gcd(m,0)=m，mmodn表示m除以n之后的余數(shù)，稱為模運(yùn)算192、算法的一個(gè)結(jié)構(gòu)化的描述計(jì)算gcd（m，n）的歐幾里得算法：第一步：假如n=0,返回m的值作為結(jié)果，同時(shí)過(guò)程結(jié)束；否則，進(jìn)入其次步。其次步：用n去除m，將余數(shù)賦給r。第三步：將n的值賦給m，將r的值賦給n，返回第一步。20ALGORITHMEuclid（m，n）//計(jì)算gcd（m，n）//輸入：非負(fù)整數(shù)m，n，其中m，n不同時(shí)為零//輸出：m，n的最大公約數(shù)whilen≠0do r ←mmodn m ←n n ←rreturnm3、算法的一個(gè)偽代碼描述214、算法的一個(gè)c++程序語(yǔ)言實(shí)現(xiàn)intEuclid（intm，intn）//計(jì)算gcd（m，n）//輸入：非負(fù)整數(shù)m，n，其中m，n不同時(shí)為零//輸出：m，n的最大公約數(shù){intr=0;if(m*n==0)return0;//m，n不符合輸入規(guī)范時(shí)返回0

while(n>0){r=mmodn; m=n; n=r;}returnm;}

22其他方法程序流程圖等，不再一一列舉。23三、算法困難性分析算法困難性是算法效率的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。算法困難性的凹凸體現(xiàn)在運(yùn)行算法所須要的計(jì)算機(jī)資源，即時(shí)間和空間（存儲(chǔ)器）資源的多少上。算法的時(shí)間困難性T(n)，空間困難性S(n)。其中n是問(wèn)題的規(guī)模（輸入大?。?4三、算法困難性分析本課程主要對(duì)算法的時(shí)間困難性進(jìn)行分析。關(guān)于算法的困難性，有兩個(gè)問(wèn)題要弄清晰：（1）用怎樣的一個(gè)量（指標(biāo)）來(lái)表達(dá)一個(gè)算法的困難性；（2）對(duì)于一個(gè)算法，怎樣具體計(jì)算它的困難性。251、算法的三種時(shí)間困難性算法的最壞、最好和平均時(shí)間困難性（1）最壞狀況下的時(shí)間困難性Tmax(n)=max{T(I)|size(I)=n}（2）最好狀況下的時(shí)間困難性Tmin(n)=min{T(I)|size(I)=n}其中size(I)=n表示I是規(guī)模為n的實(shí)例261、算法的三種時(shí)間困難性（3）平均狀況下的時(shí)間困難性Tavg(n)=其中p(I)是實(shí)例I出現(xiàn)的概率。272、算法的時(shí)間困難性計(jì)算例：依次查找算法的時(shí)間困難度計(jì)算：已知不重復(fù)，從小到大排列的m個(gè)整數(shù)的數(shù)組A[1...m],m=2K,K為正整數(shù)。對(duì)于給定的整數(shù)c,要求找到一個(gè)下標(biāo)i,使得A[i]=c.找不到返回0。

A[1]A[m]A[i]=c28分析:問(wèn)題的規(guī)模為m設(shè)元運(yùn)算執(zhí)行時(shí)間：賦值a,推斷t,加法s設(shè)c在A中查找成功292、算法的時(shí)間困難性計(jì)算

intsearch(intA[],intm,intc) {inti=1; a while(A[i]<c&&i<m)

2mt i=i+1; (m-1)(s+a) if(A[i]==c) t returni;

elsereturn0; a }30最好狀況:比較次數(shù)為1Tmin(m)=2a+2t－－時(shí)間困難度函數(shù)最壞狀況：比較次數(shù)為mTmax(m)=(m+1)a+(2m+1)t+(m-1)s平均狀況：假定全部數(shù)組元素是不同的，并且每個(gè)元素被查找的概率是相同的。則平均比較次數(shù)為(m+1)/2Tavg(m)=0.5(m+3)a+0.5(2m+3)t+0.5(m-1)s2、算法的時(shí)間困難性計(jì)算313、算法的改進(jìn)上面例子中依次查找算法的改進(jìn)有：進(jìn)行二分（折半）查找，即反復(fù)把供查找的數(shù)組分成兩半，然后在其中一半接著查找。A[1]A[m]A[mid]A[mid]>cA[mid]<c323、算法的改進(jìn)intsearch_Bin(intA[],intc,intm) {intlow=1,high=m,mid=0,found=0;while(found==0&&high>=low){mid=(low+high)/2;if(A[mid]==c)found=1; elseif(A[mid]<c)low=mid+1elsehigh=mid-1 } if(found==1)returnmid;

elsereturn0; }333、算法的改進(jìn)在最壞狀況下，查找成功時(shí)最多只需檢測(cè)A[1...m]中的∟logm」+1個(gè)重量，而改進(jìn)前最壞狀況下須要比較m個(gè)重量。如：c=5,A[1...11]={1,2,3,.....,11}對(duì)于查找算法，削減比較次數(shù)可以最有效地降低算法時(shí)間困難度。算法改進(jìn)的目的就是為了提高效率！注：本書(shū)中出現(xiàn)的logn相當(dāng)于log2n。344、時(shí)間困難性的計(jì)量算法的時(shí)間困難性計(jì)量是算法的運(yùn)算時(shí)間，但對(duì)于同一類問(wèn)題，接受算法的基本運(yùn)算次數(shù)作為算法的運(yùn)算時(shí)間?！皾h諾塔”的基本運(yùn)算是圓盤的移動(dòng)次數(shù)；查找、排序算法：元素的比較次數(shù)；矩陣相乘：兩個(gè)數(shù)的相乘；樹(shù)的搜尋：節(jié)點(diǎn)的訪問(wèn)；圖的算法：節(jié)點(diǎn)和邊的訪問(wèn)。35四、算法的漸近困難性隨著要求用計(jì)算機(jī)解決的問(wèn)題越來(lái)越困難，規(guī)模越來(lái)越大，對(duì)這類問(wèn)題的求解算法做困難性分析具有特殊重要的意義。因此，對(duì)于規(guī)模充分大，結(jié)構(gòu)又特別困難的算法，人們提出了如何簡(jiǎn)化其困難性分析，及求解其困難性函數(shù)f(n)的上界和下界的問(wèn)題。36漸近困難性的數(shù)學(xué)表述用形式簡(jiǎn)潔的函數(shù)代替形式困難的函數(shù)：T(n),asn;（這里是指充分大）(T(n)-t(n))/T(n)0，asn;t(n)是T(n)的漸近性態(tài)，為算法的漸近困難性。37漸近困難性的數(shù)學(xué)表述(T(n)-t(n))/T(n)0，asn;在數(shù)學(xué)上，t(n)是T(n)的漸近表達(dá)式，是T(n)略去低階項(xiàng)留下的主項(xiàng)。它比T(n)簡(jiǎn)潔。例如：T(n)=3n2+4nlogn+7;t(n)=3n2T(n)=4nlogn+7n;t(n)=4nlogn因此，只要考察當(dāng)問(wèn)題規(guī)模充分大時(shí)，算法困難性在漸進(jìn)意義下的階，就可以判定出哪一個(gè)算法的效率高。38為此，我們引入以下漸進(jìn)意義下的記號(hào)：

O

o

θ39（1）漸近上界記號(hào)O在下面的探討中，對(duì)全部n，時(shí)間困難性函數(shù)f(n)0，g(n)0，g(n)也稱為f(n)的階函數(shù)。漸近上界記號(hào)O——給出函數(shù)f的一個(gè)上限O(g(n))={f(n)|存在正常數(shù)c和n0使得對(duì)全部nn0有：0f(n)cg(n)}40（1）漸近上界記號(hào)O——例例1：【線性函數(shù)】考察f(n)=3n+2。當(dāng)n>=2時(shí)，3n+2<=3n+n=4n，所以f(n)=O(n)，f(n)是一個(gè)線性變更的函數(shù)。類似地，100n+6=O(n)。特殊地，當(dāng)f(n)是一個(gè)常數(shù)c時(shí)，如f(n)=9，可以記為f(n)=O(1)。41（1）漸近上界記號(hào)O——例例2：【平方函數(shù)】考察f(n2)=10n2+4n+2。當(dāng)n>=2時(shí)，10n2+4n+2<=10n2+5n

，當(dāng)n>=5時(shí)，10n2+5n<=10n2+n2

＝11n2

，所以f(n)=O(n2)。同理，對(duì)于f(n)=6×2n+n2

，f(n)=O(2n)。（當(dāng)n>=4時(shí)，n2<=2n

）42（2）漸近下界記號(hào)漸近下界記號(hào)——給出函數(shù)f的一個(gè)下限(g(n))={f(n)|存在正常數(shù)c和n0使得對(duì)全部nn0有：0cg(n)f(n)}43（2）漸近下界記號(hào)

——例例：對(duì)于全部n，有以下推導(dǎo)：∵3n+22n∴3n+2=(n)∵100n+6100n∴100n+6=(n)∵10n2+4n+210n2∴10n2+4n+2=(n2)∵6×2n+n26×2n∴6×2n+n2=(2n)。44（3）非緊上界記號(hào)o和

非緊下界記號(hào)非緊上界記號(hào)oo(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)全部nn0有：0f(n)<cg(n)}等價(jià)于f(n)/g(n)0，asn。45（3）非緊上界記號(hào)o和非緊下界記號(hào)非緊下界記號(hào)(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)全部nn0有：0cg(n)<f(n)}等價(jià)于f(n)/g(n)，asn。f(n)(g(n))g(n)o(f(n))46（3）非緊上界記號(hào)o和非緊下界記號(hào)－例例1：3n+2=o(n2)。例2：10n2+4n+2=

(n)。47（4）緊漸近界記號(hào)θ

θ(g(n))={f(n)|存在正常數(shù)c1,c2和n0使得對(duì)全部nn0有：c1g(n)f(n)c2g(n)}記號(hào)θ適用于同一個(gè)函數(shù)g既可以作為函數(shù)f的上限也可以作為f的下限的情形。定理1：θ(g(n))=O(g(n))(g(n))48（4）緊漸近界記號(hào)θ—例例：對(duì)于全部n，有：3n+2=θ(n)100n+6=θ(n)10n2+4n+2=θ(n2)6×2n+n2=θ(2n)。49Oθf(wàn)(n)=O(g(n))f(n)的階不高于g(n)的階；f(n)=(g(n))f(n)的階不低于g(n)的階；f(n)=θ(g(n))f(n)與g(n)同階。課后習(xí)題1-650O的運(yùn)算規(guī)則以下設(shè)f(n),g(n)是定義在正數(shù)集上的正函數(shù)：(1)O(f)+O(g）=O(max(f,g))(2)O(f)+O(g）=O(f+g)(3)O(f)O(g）=O(fg)(4)假如f(n)=O(g(n)),則O(f)+