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

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

—計(jì)算機(jī)科學(xué)的基石；掌握標(biāo)準(zhǔn)算法（二）從算法對(duì)于程序的重要性來(lái)講

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

—開(kāi)發(fā)分析問(wèn)題的能力3學(xué)習(xí)算法的重要性（一）從理論和實(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算法分析與設(shè)計(jì)課程

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

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

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

用科學(xué)規(guī)范的語(yǔ)言,對(duì)所求解的問(wèn)題做準(zhǔ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ò)程1)問(wèn)題的陳述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（二）問(wèn)題求解過(guò)程4)算法的正確性證明15（三）如何設(shè)計(jì)算法通過(guò)學(xué)習(xí)已被實(shí)踐證明是有用的一些基本設(shè)計(jì)策略，如遞歸、回溯等，掌握一般的算法設(shè)計(jì)方法，學(xué)會(huì)設(shè)計(jì)高效的算法。16（三）如何設(shè)計(jì)算法通過(guò)學(xué)習(xí)已被實(shí)踐證明是有用的一些基本設(shè)計(jì)策（四）如何確認(rèn)算法（證明其正確性）證明算法對(duì)所有可能的輸入都能算出正確的答案，這一工作稱(chēng)為算法確認(rèn)。這一領(lǐng)域是當(dāng)前許多計(jì)算機(jī)工作者集中研究的對(duì)象，還處于相當(dāng)初期的階段。在學(xué)習(xí)本課程中，我們僅對(duì)算法的正確性進(jìn)行一般的非形式化討論，以及對(duì)算法的程序?qū)崿F(xiàn)進(jìn)行測(cè)試驗(yàn)證。17（四）如何確認(rèn)算法（證明其正確性）證明算法對(duì)所有可能的輸入都（五）如何分析（評(píng)價(jià)）算法分析算法包括定量的分析算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間，分析算法不僅可以預(yù)計(jì)算法能否有效得完成任務(wù)，而且可以知道算法在最壞、最好和平均情況下的運(yùn)算時(shí)間，對(duì)解決同一問(wèn)題的不同算法的優(yōu)劣作出比較。18（五）如何分析（評(píng)價(jià)）算法分析算法包括定量的分析算法需要多二、算法的幾種描述方式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ù)，稱(chēng)為模運(yùn)算19二、算法的幾種描述方式1、計(jì)算兩個(gè)整數(shù)的最大公約數(shù)問(wèn)題的一個(gè)2、算法的一個(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，返回第一步。202、算法的一個(gè)結(jié)構(gòu)化的描述計(jì)算gcd（m，n）的歐幾里得算法ALGORITHMEuclid（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è)偽代碼描述21ALGORITHMEuclid（m，n）3、算法的一個(gè)偽代4、算法的一個(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;}

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

本課程主要對(duì)算法的時(shí)間復(fù)雜性進(jìn)行分析。關(guān)于算法的復(fù)雜性，有兩個(gè)問(wèn)題要弄清楚：（1）用怎樣的一個(gè)量（指標(biāo)）來(lái)表達(dá)一個(gè)算法的復(fù)雜性；（2）對(duì)于一個(gè)算法，怎樣具體計(jì)算它的復(fù)雜性。25三、算法復(fù)雜性分析本課程主要對(duì)算法的時(shí)間復(fù)雜性進(jìn)行分析。21、算法的三種時(shí)間復(fù)雜性算法的最壞、最好和平均時(shí)間復(fù)雜性（1）最壞情況下的時(shí)間復(fù)雜性

Tmax(n)=max{T(I)|size(I)=n}（2）最好情況下的時(shí)間復(fù)雜性

Tmin(n)=min{T(I)|size(I)=n}其中size(I)=n表示I是規(guī)模為n的實(shí)例261、算法的三種時(shí)間復(fù)雜性算法的最壞、最好和平均時(shí)間復(fù)雜性261、算法的三種時(shí)間復(fù)雜性（3）平均情況下的時(shí)間復(fù)雜性

Tavg(n)=

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

，asn;t(n)是T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。37漸近復(fù)雜性的數(shù)學(xué)表述用形式簡(jiǎn)單的函數(shù)代替形式復(fù)雜的函數(shù)：37漸近復(fù)雜性的數(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)=3n2

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

O

o

θ39為此，我們引入以下漸進(jìn)意義下的記號(hào)：39（1）漸近上界記號(hào)O在下面的討論中，對(duì)所有n，時(shí)間復(fù)雜性函數(shù)f(n)0，g(n)0，g(n)也稱(chēng)為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在下面的討論中，對(duì)所有n，時(shí)間復(fù)雜性函數(shù)（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ù)。類(lèi)似地，100n+6=O(n)。特別地，當(dāng)f(n)是一個(gè)常數(shù)c時(shí)，如f(n)=9，可以記為f(n)=O(1)。41（1）漸近上界記號(hào)O——例例1：【線性函數(shù)】考察f(n)=3（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（1）漸近上界記號(hào)O——例例2：【平方函數(shù)】考察f(n2)=（2）漸近下界記號(hào)漸近下界記號(hào)

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

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

cg(n)

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

——例例：對(duì)于所有n，有以下推導(dǎo)：∵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）漸近下界記號(hào)——例例：對(duì)于所有n，有以下推導(dǎo)：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)o45（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)非緊下界記號(hào)46（3）非緊上界記號(hào)o和非緊下界記號(hào)－例例1：3n+2=o(n2)。例2：10n2+4n+2=

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