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

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

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

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

證明算法對一切合法輸入均能在有限次計算后產(chǎn)生正確輸出.5)算法的程序?qū)崿F(xiàn)將算法正確地編寫成機(jī)器語言程序.6)算法分析對執(zhí)行該算法所消耗的計算機(jī)資源進(jìn)行估算.15（三）如何設(shè)計算法通過學(xué)習(xí)已被實踐證明是有用的一些基本設(shè)計策略，如遞歸、回溯等，駕馭一般的算法設(shè)計方法，學(xué)會設(shè)計高效的算法。16（四）如何確認(rèn)算法（證明其正確性）證明算法對全部可能的輸入都能算出正確的答案，這一工作稱為算法確認(rèn)。這一領(lǐng)域是當(dāng)前很多計算機(jī)工作者集中探討的對象，還處于相當(dāng)時期的階段。在學(xué)習(xí)本課程中，我們僅對算法的正確性進(jìn)行一般的非形式化探討，以及對算法的程序?qū)崿F(xiàn)進(jìn)行測試驗證。17（五）如何分析（評價）算法分析算法包括定量的分析算法須要多少計算時間和存儲空間，分析算法不僅可以預(yù)料算法能否有效得完成任務(wù)，而且可以知道算法在最壞、最好和平均狀況下的運算時間，對解決同一問題的不同算法的優(yōu)劣作出比較。18二、算法的幾種描述方式1、計算兩個整數(shù)的最大公約數(shù)問題的一個現(xiàn)代數(shù)學(xué)術(shù)語表述歐幾里得算法基于的方法是重復(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ù)，稱為模運算192、算法的一個結(jié)構(gòu)化的描述計算gcd（m，n）的歐幾里得算法：第一步：假如n=0,返回m的值作為結(jié)果，同時過程結(jié)束；否則，進(jìn)入其次步。其次步：用n去除m，將余數(shù)賦給r。第三步：將n的值賦給m，將r的值賦給n，返回第一步。20ALGORITHMEuclid（m，n）//計算gcd（m，n）//輸入：非負(fù)整數(shù)m，n，其中m，n不同時為零//輸出：m，n的最大公約數(shù)whilen≠0do r ←mmodn m ←n n ←rreturnm3、算法的一個偽代碼描述214、算法的一個c++程序語言實現(xiàn)intEuclid（intm，intn）//計算gcd（m，n）//輸入：非負(fù)整數(shù)m，n，其中m，n不同時為零//輸出：m，n的最大公約數(shù){intr=0;if(m*n==0)return0;//m，n不符合輸入規(guī)范時返回0

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

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

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

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

O

o

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

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

＝11n2

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

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

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

——例例：對于全部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）非緊上界記號o和

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

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

θ(g(n))={f(n)|存在正常數(shù)c1,c2和n0使得對全部nn0有：c1g(n)f(n)c2g(n)}記號θ適用于同一個函數(shù)g既可以作為函數(shù)f的上限也可以作為f的下限的情形。定理1：θ(g(n))=O(g(n))(g(n))48（4）緊漸近界記號θ—例例：對于全部n，有：3n+2=θ(n)100n+6=θ(n)10n2+4n+2=θ(n2)6×2n+n2=θ(2n)。49Oθf(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的運算規(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)+