《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語(yǔ)言描述） 課件 第1章 緒論

教材：《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語(yǔ)言描述），李春葆等清華大學(xué)出版社20241/49第1章算法入門—概論1.1算法的概念1.2算法分析CONTENTS提綱2/49算法（algorithm）是求解問(wèn)題的一系列計(jì)算步驟，是一個(gè)由若干運(yùn)算或指令組成的有限序列，用來(lái)將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果。算法輸入輸出1.1.1什么是算法1.1算法的概念3/49算法的5大特性有窮性：在有限步之后結(jié)束。確定性：每一條指令必須有確切的含義，不會(huì)產(chǎn)生二義性?？尚行裕喝藗儍H用筆和紙做有限次運(yùn)算就能完成。輸入：有零個(gè)或多個(gè)輸入。輸出：有一個(gè)或多個(gè)輸出。4/49算法（有窮性、確定性、可行性）輸入輸出求解問(wèn)題5/49【例1-1】有下列兩段描述：

描述1：

描述2：defexam1(): defexam2(): n=2 y=0 whilen%2==0:n=n+2 x=5/y print(n) println(x)違反有窮性違反可行性6/49算法設(shè)計(jì)要求正確性：對(duì)指定的每個(gè)輸入實(shí)例都能輸出正確的結(jié)果并停止。可使用性：用戶友好性。可讀性：算法邏輯清晰、簡(jiǎn)單和結(jié)構(gòu)化。健壯性：容錯(cuò)性。高效率與低存儲(chǔ)量：好的時(shí)空性能。7/491.1.2算法描述Python語(yǔ)言描述算法一般形式采用Python實(shí)現(xiàn)算法。Python中方法的參數(shù)分為引用類型和基本數(shù)據(jù)類型（非引用類型）。在方法調(diào)用時(shí)基本數(shù)據(jù)類型參數(shù)只會(huì)執(zhí)行實(shí)參到形參的單向值傳遞，執(zhí)行方法中這類參數(shù)的改變不會(huì)回傳給對(duì)應(yīng)的實(shí)參。8/49Sum問(wèn)題：求s=1+2+…+n。1=11+2=31+2+3=61+2+3+4=10…9/491 defSum1(n,s):2 ifn<=0:returnFalse #參數(shù)錯(cuò)誤時(shí)返回假3 foriinrange(1,n+1):s+=i4 returnTrue #參數(shù)正確時(shí)計(jì)算出結(jié)果并返回真Sum問(wèn)題：求s=1+2+…+n。1 n,b=10,02 ret=Sum1(n,b)3 print("ret:%s,b:%d"%(ret,b))輸出結(jié)果“ret:True，b:0”顯然結(jié)果是錯(cuò)誤10/491 defSum2(n,sl):2 ifn<=0:returnFalse #參數(shù)錯(cuò)誤時(shí)返回假3 sl[0]=04 foriinrange(1,n+1):sl[0]+=i5 returnTrue #參數(shù)正確時(shí)計(jì)算出結(jié)果并返回真改正：1 n,b=10,[0]2 ret=Sum2(n,b)3 print("ret:%s,b:%d"%(ret,b[0]))輸出結(jié)果“ret:True，b:55”O(jiān)K!11/49對(duì)于一些簡(jiǎn)單的算法：只有一個(gè)輸出并且通過(guò)約束輸入總能夠得到正確結(jié)果時(shí)，可以直接用方法返回值表示輸出，這樣會(huì)簡(jiǎn)化算法設(shè)計(jì)！1 defSum3(n):2 s=03 foriinrange(1,n+1):s+=i4 returns1 n=102 print("b:%d"%(Sum3(n)))輸出結(jié)果“b:55”O(jiān)K!12/491.1.3算法和數(shù)據(jù)結(jié)構(gòu)程序=數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)結(jié)構(gòu)是算法設(shè)計(jì)的基礎(chǔ)。算法的操作對(duì)象是數(shù)據(jù)結(jié)構(gòu)。在設(shè)計(jì)算法時(shí)通常要構(gòu)建適合這種算法的數(shù)據(jù)結(jié)構(gòu)。13/491.1.4算法設(shè)計(jì)的基本步驟分析求解問(wèn)題選擇數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)策略描述算法證明算法正確性算法分析建立數(shù)學(xué)模型14/491.2算法分析1.2.1算法時(shí)間復(fù)雜度分析1.什么是算法時(shí)間復(fù)雜度分析事前分析估算法：認(rèn)為算法的“運(yùn)行工作量”的大小只依賴于問(wèn)題規(guī)模n，或者說(shuō)它是問(wèn)題規(guī)模的函數(shù)。算法執(zhí)行時(shí)間是算法中所有語(yǔ)句的執(zhí)行時(shí)間之和，顯然與算法中所有語(yǔ)句的執(zhí)行次數(shù)成正比，可以簡(jiǎn)單地用算法中基本操作的執(zhí)行次數(shù)來(lái)度量。算法中的基本操作是指最深層循環(huán)內(nèi)的原操作，它對(duì)算法執(zhí)行時(shí)間的貢獻(xiàn)最大，是算法中最重要的操作。算法中所有基本操作的執(zhí)行次數(shù)為f(n)。15/49算法時(shí)間復(fù)雜度分析是一種漸進(jìn)分析，是指當(dāng)問(wèn)題規(guī)模n很大并趨于無(wú)窮大時(shí)對(duì)算法的時(shí)間性能分析，可表示為同時(shí)忽略低階項(xiàng)和最高階系數(shù)。16/49算法分析問(wèn)題規(guī)模n，找出其中的基本語(yǔ)句，求出其運(yùn)算次數(shù)f(n)用大O、大

或大

表示算法分析17/49上界定義：

f(n)=O(g(n))（讀作“f(n)是g(n)的大O”），其含義是存在正常量c和n0，使得n≥n0有0≤f(n)≤cg(n)。也就是說(shuō)f(n)的階不高于g(n)的階，稱g(n)為f(n)的上界。cg(n)f(n)nf(n)=O(g(n))n018/49可以利用極限來(lái)證明：如果=c并且c≠∞，則有f(n)=O(g(n))。19/49一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0（am>0），有f(n)=O(nm)。例如3n+2=O(n)，因?yàn)?/p>

成立。10n2+4n+2=O(n4)，因?yàn)?/p>

成立。=c≠∞，則有f(n)=O(g(n))。20/49示例對(duì)于f(n)=2n，g(n)=n!，確定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=

(g(n))，并簡(jiǎn)要說(shuō)明理由。f(n)=O(g(n))，因?yàn)閒(n)的階低于g(n)的階。解：或者21/49下界定義：

f(n)=

(g(n))（讀作“f(n)是g(n)的大

”），其含義是存在正常量c和n0，使得n≥n0時(shí)f(n)≥cg(n)。也就是說(shuō)f(n)的階不低于g(n)的階，稱g(n)為f(n)的下界。f(n)cg(n)nf(n)=

(g(n))n022/49可以利用極限來(lái)證明：如果=c并且c≠0，則有f(n)=

(g(n))。23/49=c≠0，則有f(n)=

(g(n))。一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0（am>0），有f(n)=

(nm)。例如3n+2=

(n)，因?yàn)?/p>

成立。10n2+4n+2=

(n)，因?yàn)?/p>

成立。24/49示例對(duì)于f(n)=3n，g(n)=2n，確定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=

(g(n))，并簡(jiǎn)要說(shuō)明理由。f(n)=Ω(g(n))，因?yàn)閒(n)的階高于g(n)的階。解：或者≠0。25/49確界定義：

f(n)=

(g(n))（讀作“f(n)是g(n)的大

”），其含義是存在正常量c1、c2和n0，使得n≥n0時(shí)有c1g(n)≤f(n)≤c2g(n)。也就是說(shuō)g(n)與f(n)的同階，也稱g(n)為f(n)的確界。c2g(n)c1g(n)f(n)n0nf(n)=

(g(n))26/49可以利用極限來(lái)證明：如果=c并且0<c<∞，則有f(n)=

(g(n))。27/49，0<c<∞，則有f(n)=

(g(n))。例如3n+2=

(n)。10n2+4n+2=

(n2)。一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0（am>0），有f(n)=

(nm)。28/49證明2n+1=

(2n)關(guān)系成立。示例證明：c=2，c≠0并且c≠∞2n+1=

(2n)29/49大

符號(hào)比大O符號(hào)和大

符號(hào)都要精確，f(n)=

(g(n))隱含著f(n)=O(g(n))和f(n)=

(g(n))。目前國(guó)內(nèi)大部分教科書(shū)中習(xí)慣使用大O符號(hào)（實(shí)際上指最接近的那個(gè)上界），本書(shū)主要也采用這種表示形式。說(shuō)明30/494.算法的最好、最壞和平均情況分析

定義4設(shè)一個(gè)算法的輸入規(guī)模為n，Dn是所有輸入的集合，任一輸入I∈Dn，P(I)是I出現(xiàn)的概率，有P(I)=1，T(I)是算法在輸入I下所執(zhí)行的基本操作次數(shù)，則該算法的平均執(zhí)行時(shí)間為A(n)=

I∈DnP(I)*T(I)對(duì)應(yīng)的時(shí)間復(fù)雜度稱為平均時(shí)間復(fù)雜度。平均時(shí)間復(fù)雜度反映算法的總體時(shí)間性能。31/49算法的最好情況為G(n)=minI∈DnT(I)，是指算法在所有輸入I下所執(zhí)行基本操作的最少執(zhí)行次數(shù)。對(duì)應(yīng)的時(shí)間復(fù)雜度稱為最好時(shí)間復(fù)雜度，最好時(shí)間復(fù)雜度反映算法的最佳性能，即為算法的時(shí)間下界。算法的最壞情況為W(n)=maxI∈DnT(I)，是指算法在所有輸入I下所執(zhí)行基本操作的最大執(zhí)行次數(shù)。對(duì)應(yīng)的時(shí)間復(fù)雜度稱為最懷時(shí)間復(fù)雜度，最懷時(shí)間復(fù)雜度為算法的時(shí)間上界。32/49【例1-4】設(shè)計(jì)一個(gè)盡可能高效的算法，在長(zhǎng)度為n的一維整型數(shù)組a[0..n-1]中查找值最大的元素maxe和值最小的元素mine。并分析算法的最好、最壞和平均時(shí)間復(fù)雜度。解1 defMaxMin(a,n):2 maxe,mine=a[0],a[0]3 foriinrange(1,n):4 ifa[i]>maxe:maxe=a[i]5 elifa[i]<mine:mine=a[i];6 print("maxe=%d,mine=%d"%(maxe,mine))33/49該算法的基本語(yǔ)句是元素比較。最好的情況是a中元素遞增排列，元素比較次數(shù)為n-1，即G(n)=n-1=O(n)。1 defMaxMin(a,n):2 maxe,mine=a[0],a[0]3 foriinrange(1,n):4 ifa[i]>maxe:maxe=a[i]5 elifa[i]<mine:mine=a[i];6 print("maxe=%d,mine=%d"%(maxe,mine))34/49最壞的情況是a中元素遞減排列，元素比較次數(shù)為2(n-1)，即W(n)=2(n-1)=O(n)。1 defMaxMin(a,n):2 maxe,mine=a[0],a[0]3 foriinrange(1,n):4 ifa[i]>maxe:maxe=a[i]5 elifa[i]<mine:mine=a[i];6 print("maxe=%d,mine=%d"%(maxe,mine))35/49平均情況：a中有一半的元素比maxe大，a[i]>maxe比較執(zhí)行n-1次，a[i]<mine比較執(zhí)行(n-1)/2次，因此平均元素比較次數(shù)為3(n-1)/2，即A(n)=3(n-1)/2=O(n)。1 defMaxMin(a,n):2 maxe,mine=a[0],a[0]3 foriinrange(1,n):4 ifa[i]>maxe:maxe=a[i]5 elifa[i]<mine:mine=a[i];6 print("maxe=%d,mine=%d"%(maxe,mine))36/49【例1-5】采用順序查找方法，在長(zhǎng)度為n的一維整數(shù)數(shù)組a[0..n-1]中查找值為x的元素，即從數(shù)組的第一個(gè)元素開(kāi)始，逐個(gè)與被查值x進(jìn)行比較。找到后返回True，否則返回False，對(duì)應(yīng)的算法如下：1 defFind(a,n,x):2 i=03 whilei<n:4 ifa[i]==x:break5 i+=16 ifi<n:returnTrue7 else:returnFalse37/491 defFind(a,n,x):2 i=03 whilei<n:4 ifa[i]==x:break5 i+=16 ifi<n:returnTrue7 else:returnFalse回答以下問(wèn)題：

（1）分析該算法在等概率情況下成功查找到值為x的元素的最好、最壞和平均時(shí)間復(fù)雜度。

（2）假設(shè)被查值x在數(shù)組a中的概率是p，不在數(shù)組a中的概率是1-p，求算法的平均時(shí)間復(fù)雜度。38/49（1）僅考慮查找成功的情況。

算法的while循環(huán)中if語(yǔ)句是基本操作（用于元素比較）。a數(shù)組中有n個(gè)元素，當(dāng)?shù)谝粋€(gè)元素a[0]等于x，此時(shí)基本操作僅執(zhí)行一次，此時(shí)呈現(xiàn)最好的情況，即G(n)=1=O(1)。

當(dāng)a中最后一個(gè)元素a[n-1]等于x，此時(shí)基本操作執(zhí)行n次，此時(shí)呈現(xiàn)最壞的情況，即W(n)=n=O(n)。解1 defFind(a,n,x):2 i=03 whilei<n:4 ifa[i]==x:break5 i+=16 ifi<n:returnTrue7 else:returnFalse39/49對(duì)于成功查找的平均情況，假設(shè)查找到每個(gè)元素的概率相同，則P(a[i])=1/n（0≤i≤n-1），而成功找到a[i]元素時(shí)基本操作正好執(zhí)行i+1次。

所以：1 defFind(a,n,x):2 i=03 whilei<n:4 ifa[i]==x:break5 i+=16 ifi<n:returnTrue7 else:returnFalse40/49（2）這里是既考慮成功查找又考慮不成功查找的情況。

對(duì)于成功查找，被查值x在數(shù)組a中的概率為p時(shí)，算法執(zhí)行有n種成功情況，在等概率情況下元素a[i]被查找到的概率P(a[i])=p/n，成功找到a[i]元素時(shí)基本操作執(zhí)行i+1次。

對(duì)于不成功查找，其概率為1-p，所有不成功查找基本操作都只執(zhí)行n次，不妨看成一種情況。41/49如果已知查找的x有一半的機(jī)會(huì)在數(shù)組中，此時(shí)p=1/2，則A(n)=[(n+1)/4]+n/2≈3n/4。42/494.平攤分析考慮這樣一種算法，在算法中有一種操作反復(fù)執(zhí)行時(shí)有這樣的特性，其運(yùn)行時(shí)間始終變動(dòng)，如果這一操作在大多數(shù)時(shí)候運(yùn)行很快，只是偶爾要花費(fèi)大量時(shí)間，對(duì)這樣的算法可以采用平攤分析。在平攤分析中，執(zhí)行一系列數(shù)據(jù)結(jié)構(gòu)操作所需要的時(shí)間是通過(guò)對(duì)執(zhí)行的所有操作求平均而得出的。平攤分析可用來(lái)證明在一系列操作中，即使單一的操作具有較大的代價(jià)，通過(guò)對(duì)所有操作求平均后，平均代價(jià)還是很小的。平攤分析與平均情況分析的不同之處在于它不牽涉到概率。這種分析保證了在最壞情況下每個(gè)操作具有平均性能。43/49【例1-6】假設(shè)有一個(gè)可以存放若干個(gè)整數(shù)的整數(shù)表，其類為IntList，data域是存放整數(shù)元素的列表，capacity域表示data的容量（data列表中能夠存放的最多元素個(gè)數(shù)，初始容量為常數(shù)m），length域表示長(zhǎng)度（data列表中存放的實(shí)際元素個(gè)數(shù)）。1 classIntList:#整數(shù)表類2 m=2 #初始容量3 def__init__(self): #構(gòu)造方法4 self.capacity=self.m #容量5 self.data=[0]*self.m6 self.length=0 #長(zhǎng)度

整數(shù)表提供有這些運(yùn)算，構(gòu)造方法用于初始化，即設(shè)置初始容量、分配初始空間和將長(zhǎng)度置為0。44/497 defExpand(self): #按長(zhǎng)度兩倍擴(kuò)大容量8 self.capacity=2*self.length #設(shè)置新容量9 newdata=[0]*self.capacity10 foriinrange(0,self.length): #復(fù)制全部元素11 newdata[i]=self.data[i]12 self.data=newdata方法Expand()用于擴(kuò)大容量，當(dāng)長(zhǎng)度達(dá)到容量時(shí)置新容量為兩倍長(zhǎng)度。45/4913 defAdd(self,e):