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

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

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

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

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之后的余數，稱為模運算192、算法的一個結構化的描述計算gcd（m，n）的歐幾里得算法：第一步：假如n=0,返回m的值作為結果，同時過程結束；否則，進入其次步。其次步：用n去除m，將余數賦給r。第三步：將n的值賦給m，將r的值賦給n，返回第一步。20ALGORITHMEuclid（m，n）//計算gcd（m，n）//輸入：非負整數m，n，其中m，n不同時為零//輸出：m，n的最大公約數whilen≠0do r ←mmodn m ←n n ←rreturnm3、算法的一個偽代碼描述214、算法的一個c++程序語言實現intEuclid（intm，intn）//計算gcd（m，n）//輸入：非負整數m，n，其中m，n不同時為零//輸出：m，n的最大公約數{intr=0;if(m*n==0)return0;//m，n不符合輸入規范時返回0

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

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

A[1]A[m]A[i]=c28分析:問題的規模為m設元運算執行時間：賦值a,推斷t,加法s設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最好狀況:比較次數為1Tmin(m)=2a+2t－－時間困難度函數最壞狀況：比較次數為mTmax(m)=(m+1)a+(2m+1)t+(m-1)s平均狀況：假定全部數組元素是不同的，并且每個元素被查找的概率是相同的。則平均比較次數為(m+1)/2Tavg(m)=0.5(m+3)a+0.5(2m+3)t+0.5(m-1)s2、算法的時間困難性計算313、算法的改進上面例子中依次查找算法的改進有：進行二分（折半）查找，即反復把供查找的數組分成兩半，然后在其中一半接著查找。A[1]A[m]A[mid]A[mid]>cA[mid]<c323、算法的改進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、算法的改進在最壞狀況下，查找成功時最多只需檢測A[1...m]中的∟logm」+1個重量，而改進前最壞狀況下須要比較m個重量。如：c=5,A[1...11]={1,2,3,.....,11}對于查找算法，削減比較次數可以最有效地降低算法時間困難度。算法改進的目的就是為了提高效率！注：本書中出現的logn相當于log2n。344、時間困難性的計量算法的時間困難性計量是算法的運算時間，但對于同一類問題，接受算法的基本運算次數作為算法的運算時間。“漢諾塔”的基本運算是圓盤的移動次數；查找、排序算法：元素的比較次數；矩陣相乘：兩個數的相乘；樹的搜尋：節點的訪問；圖的算法：節點和邊的訪問。35四、算法的漸近困難性隨著要求用計算機解決的問題越來越困難，規模越來越大，對這類問題的求解算法做困難性分析具有特殊重要的意義。因此，對于規模充分大，結構又特別困難的算法，人們提出了如何簡化其困難性分析，及求解其困難性函數f(n)的上界和下界的問題。36漸近困難性的數學表述用形式簡潔的函數代替形式困難的函數：T(n),asn;（這里是指充分大）(T(n)-t(n))/T(n)0，asn;t(n)是T(n)的漸近性態，為算法的漸近困難性。37漸近困難性的數學表述(T(n)-t(n))/T(n)0，asn;在數學上，t(n)是T(n)的漸近表達式，是T(n)略去低階項留下的主項。它比T(n)簡潔。例如：T(n)=3n2+4nlogn+7;t(n)=3n2T(n)=4nlogn+7n;t(n)=4nlogn因此，只要考察當問題規模充分大時，算法困難性在漸進意義下的階，就可以判定出哪一個算法的效率高。38為此，我們引入以下漸進意義下的記號：

O

o

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

，當n>=5時，10n2+5n<=10n2+n2

＝11n2

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

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

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

——例例：對于全部n，有以下推導：∵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)|對于任何正常數c>0，存在正數和n0>0使得對全部nn0有：0f(n)<cg(n)}等價于f(n)/g(n)0，asn。45（3）非緊上界記號o和非緊下界記號非緊下界記號(g(n))={f(n)|對于任何正常數c>0，存在正數和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)|存在正常數c1,c2和n0使得對全部nn0有：c1g(n)f(n)c2g(n)}記號θ適用于同一個函數g既可以作為函數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)同階。課后習題1-650O的運算規則以下設f(n),g(n)是定義在正數集上的正函數：(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)+