課程安排理論課：1～10周，40學時周二(5-6)、周五(1-2)上機：18學時期末考試：閉卷筆試，第11周上課點名三次不到者取消考試資格；遲到或作業(yè)缺交，一次扣10分（平時成績）。1課程安排理論課：1～10周，40學時1教學目的和要求本課程是計算機類專業(yè)的專業(yè)基礎課程；通過課程學習和上機實踐，對計算機常用算法有一個較全面的了解，掌握通用算法的一般設計方法；學會對算法的時間、空間復雜度分析，掌握提高算法效率的方法和途徑。2教學目的和要求本課程是計算機類專業(yè)的專業(yè)基礎課程；2學習算法的重要性（一）從理論和實踐的角度理解

—計算機科學的基石；掌握標準算法（二）從算法對于程序的重要性來講

—皮之不存，毛將附焉？（三）從對同學們的能力培養(yǎng)看

—開發(fā)分析問題的能力3學習算法的重要性（一）從理論和實踐的角度理解3算法分析與設計課程

與數(shù)據(jù)結(jié)構課程（一）數(shù)據(jù)結(jié)構關心的對象各種數(shù)據(jù)結(jié)構的作用和效率、具體的問題（二）算法設計與分析關心的對象算法設計技術的適用性和效率、一般性方法4算法分析與設計課程

與數(shù)據(jù)結(jié)構課程（一）數(shù)據(jù)結(jié)構關心的對象授課內(nèi)容第1章算法概述第2章遞歸與分治策略第3章動態(tài)規(guī)劃第4章貪心算法第5章回溯法第6章分支限界法*7-9章屬研究生學習內(nèi)容，可自學了解。5授課內(nèi)容第1章算法概述5第1章算法概述學習要點:

一、理解算法的概念，以及問題求解的過程。二、掌握算法的幾種描述方式。三、理解算法的計算復雜性概念。四、掌握算法漸近復雜性的數(shù)學表述。6第1章算法概述學習要點:6什么是算法？我們來編寫一個燒開水的算法：輸入自來水循環(huán)（反復）加熱直到水開輸出開水7什么是算法？我們來編寫一個燒開水的算法：7一、算法(Algorithm)

算法概念：通俗地講，算法是指解決問題的一種方法或一個過程。嚴格地講，算法是由若干條指令組成的有窮序列。圖1.1算法的概念圖8一、算法(Algorithm)算法概念：通俗地（一）算法的性質(zhì)1、算法具有某些特性，如下幾條：(1)輸入：有零個或多個外部提供的量作為算法的輸入。(2)輸出：算法產(chǎn)生至少一個量作為輸出。這些輸出是和輸入有某種特定關系的量。9（一）算法的性質(zhì)1、算法具有某些特性，如下幾條：9（一）算法的性質(zhì)(3)確定性：組成算法的每條指令是清晰，無歧義的。(4)有限性（有窮性）：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時間也是有限的。10（一）算法的性質(zhì)(3)確定性：組成算法的每條指令是清晰，無歧（一）算法的性質(zhì)(5)可實現(xiàn)性：此性質(zhì)是指算法中有待實現(xiàn)的運算都是相當基本的，每種運算至少在原理上能由人用紙和筆在有限的時間內(nèi)完成。（補充）11（一）算法的性質(zhì)(5)可實現(xiàn)性：此性質(zhì)是指算法中有待實現(xiàn)的運（一）算法性質(zhì)2、關于算法有幾個要點：(1)算法所處理的輸入的值域必須嚴格定義。(2)同樣一種算法可以用幾種不同的形式來描述。12（一）算法性質(zhì)2、關于算法有幾個要點：12（一）算法性質(zhì)(3)同一個問題可以存在多種解決的算法。(4)同一個問題的幾種算法可能會基于完全不同的解題思路，而且解題速度也會有顯著不同。13（一）算法性質(zhì)(3)同一個問題可以存在多種解決的算法。13（二）問題求解過程1)問題的陳述

用科學規(guī)范的語言,對所求解的問題做準確的描述.2)建立數(shù)學模型通過對問題的分析,找出其中的所有操作對象及操作對象之間的關系并用數(shù)學語言加以描述.3)算法設計根據(jù)數(shù)學模型設計問題的計算機求解算法.14（二）問題求解過程1)問題的陳述14（二）問題求解過程4)算法的正確性證明

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

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ù)，稱為模運算19二、算法的幾種描述方式1、計算兩個整數(shù)的最大公約數(shù)問題的一個2、算法的一個結(jié)構化的描述計算gcd（m，n）的歐幾里得算法：第一步：如果n=0,返回m的值作為結(jié)果，同時過程結(jié)束；否則，進入第二步。第二步：用n去除m，將余數(shù)賦給r。第三步：將n的值賦給m，將r的值賦給n，返回第一步。202、算法的一個結(jié)構化的描述計算gcd（m，n）的歐幾里得算法ALGORITHMEuclid（m，n）//計算gcd（m，n）//輸入：非負整數(shù)m，n，其中m，n不同時為零//輸出：m，n的最大公約數(shù)whilen≠0do r ←mmodn m ←n n ←rreturnm3、算法的一個偽代碼描述21ALGORITHMEuclid（m，n）3、算法的一個偽代4、算法的一個c++程序語言實現(xiàn)intEuclid（intm，intn）//計算gcd（m，n）//輸入：非負整數(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;}

224、算法的一個c++程序語言實現(xiàn)intEuclid（int其他方法程序流程圖等，不再一一列舉。23其他方法程序流程圖等，不再一一列舉。23三、算法復雜性分析算法復雜性是算法效率的度量，是評價算法優(yōu)劣的重要依據(jù)。算法復雜性的高低體現(xiàn)在運行算法所需要的計算機資源，即時間和空間（存儲器）資源的多少上。算法的時間復雜性T(n)，空間復雜性S(n)。其中n是問題的規(guī)模（輸入大小）。24三、算法復雜性分析算法復雜性是算法效率的度量，是評價算法優(yōu)劣三、算法復雜性分析

本課程主要對算法的時間復雜性進行分析。關于算法的復雜性，有兩個問題要弄清楚：（1）用怎樣的一個量（指標）來表達一個算法的復雜性；（2）對于一個算法，怎樣具體計算它的復雜性。25三、算法復雜性分析本課程主要對算法的時間復雜性進行分析。21、算法的三種時間復雜性算法的最壞、最好和平均時間復雜性（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、算法的三種時間復雜性算法的最壞、最好和平均時間復雜性261、算法的三種時間復雜性（3）平均情況下的時間復雜性

Tavg(n)=

其中p(I)是實例I出現(xiàn)的概率。271、算法的三種時間復雜性（3）平均情況下的時間復雜性272、算法的時間復雜性計算例：順序查找算法的時間復雜度計算：

已知不重復，從小到大排列的m個整數(shù)的數(shù)組A[1...m],m=2K,K為正整數(shù)。對于給定的整數(shù)c,要求找到一個下標i,使得A[i]=c.找不到返回0。

A[1]A[m]A[i]=c282、算法的時間復雜性計算例：順序查找算法的時間復雜度計算：A分析:問題的規(guī)模為m設元運算執(zhí)行時間：賦值a,判斷t,加法s設c在A中查找成功29分析: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 }302、算法的時間復雜性計算intsearch(int最好情況:比較次數(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、算法的時間復雜性計算31最好情況:比較次數(shù)為12、算法的時間復雜性計算313、算法的改進上面例子中順序查找算法的改進有：進行二分（折半）查找，即反復把供查找的數(shù)組分成兩半，然后在其中一半繼續(xù)查找。A[1]A[m]A[mid]A[mid]>cA[mid]<c323、算法的改進上面例子中順序查找算法的改進有：A[1]A[m3、算法的改進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、算法的改進intsearch_Bin(intA[]3、算法的改進在最壞情況下，查找成功時最多只需檢測A[1...m]中的∟logm」+1個分量，而改進前最壞情況下需要比較m個分量。如：c=5,A[1...11]={1,2,3,.....,11}對于查找算法，減少比較次數(shù)可以最有效地降低算法時間復雜度。算法改進的目的就是為了提高效率！注：本書中出現(xiàn)的logn相當于log2n。343、算法的改進在最壞情況下，查找成功時最多只需檢測A[1.4、時間復雜性的計量算法的時間復雜性計量是算法的運算時間，但對于同一類問題，采用算法的基本運算次數(shù)作為算法的運算時間。“漢諾塔”的基本運算是圓盤的移動次數(shù)；查找、排序算法：元素的比較次數(shù)；矩陣相乘：兩個數(shù)的相乘；樹的搜索：節(jié)點的訪問；圖的算法：節(jié)點和邊的訪問。354、時間復雜性的計量算法的時間復雜性計量是算法的運算時間，但四、算法的漸近復雜性隨著要求用計算機解決的問題越來越復雜，規(guī)模越來越大，對這類問題的求解算法做復雜性分析具有特別重要的意義。因此，對于規(guī)模充分大，結(jié)構又十分復雜的算法，人們提出了如何簡化其復雜性分析，及求解其復雜性函數(shù)f(n)的上界和下界的問題。36四、算法的漸近復雜性隨著要求用計算機解決的問題越來越復雜，規(guī)漸近復雜性的數(shù)學表述用形式簡單的函數(shù)代替形式復雜的函數(shù)：T(n),asn;（這里是指充分大）(T(n)-t(n))/T(n)0

，asn;t(n)是T(n)的漸近性態(tài)，為算法的漸近復雜性。37漸近復雜性的數(shù)學表述用形式簡單的函數(shù)代替形式復雜的函數(shù)：37漸近復雜性的數(shù)學表述(T(n)-t(n))/T(n)0

，asn;在數(shù)學上，t(n)是T(n)的漸近表達式，是T(n)略去低階項留下的主項。它比T(n)簡單。例如：T(n)=3n2+4nlogn+7;t(n)=3n2

T(n)=4nlogn+7n;t(n)=4nlogn因此，只要考察當問題規(guī)模充分大時，算法復雜性在漸進意義下的階，就可以判定出哪一個算法的效率高。38漸近復雜性的數(shù)學表述(T(n)-t(n))/T(n)為此，我們引入以下漸進意義下的記號：

O

o

θ39為此，我們引入以下漸進意義下的記號：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在下面的討論中，對所有n，時間復雜性函數(shù)（1）漸近上界記號O——例例1：【線性函數(shù)】考察f(n)=3n+2。當n>=2時，3n+2<=3n+n=4n，所以f(n)=O(n)，f(n)是一個線性變化的函數(shù)。類似地，100n+6=O(n)。特別地，當f(n)是一個常數(shù)c時，如f(n)=9，可以記為f(n)=O(1)。41（1）漸近上界記號O——例例1：【線性函數(shù)】考察f(n)=3（1）漸近上界記號O——例例2：【平方函數(shù)】考察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（1）漸近上界記號O——例例2：【平方函數(shù)】考察f(n2)=（2）漸近下界記號漸近下界記號

——給出函數(shù)f的一個下限

(g(n))={f(n)|存在正常數(shù)c和n0使得對所有nn0有：0

cg(n)

f(n)}43（2）漸近下界記號漸近下界記號——給出函數(shù)f的一個下限（2）漸近下界記號

——例例：對于所有n，有以下推導：∵3n+22n∴3n+2=(n)∵100n+6100n∴

100n+6=(n)∵10n2+4n+2

10n2

∴

10n2+4n+2=(n2)∵6×2n+n2

6×2n

∴6×2n+n2=(2n)。44（2）漸近下界記號——例例：對于所有n，有以下推導：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和

非緊下界記號非緊上界記號o45（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和非緊下界記號非緊下界記號46（3）非緊上界記號o和非緊下界記號－例例1：3n+2=o(n2)。例2：10n2+4n+2=

(n)。47（3）非緊上界記號o和非緊下界記號－例例1：3n+2=（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）緊漸近界記號θθ(g(n))={f(n)|（4）緊漸近界記號θ—例例：對于所有n，有：3n+2=θ(n)100n+6=θ(n)10n2+4n+2=θ(n2)6×2n+n2=θ(2n)。49（4）緊漸近界記號θ—例例：對于所有n，有：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)=O(g(n))O的運算規(guī)則以下設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)+O(g)=O(g)(5)O(cf(n))=O(f(n)),其中c是一個正的常數(shù)(6)f=O(f)51O的運算規(guī)則以下設f(n),g(n)是定義在正數(shù)集上的正函數(shù)