計(jì)算理論與算法分析設(shè)計(jì)課件：算法概述

計(jì)算理論與算法分析設(shè)計(jì)2024/7/52

of158前言旅行商問題TravelingSalesmanProblem(TSP):

設(shè)有n個城市，已知任意兩城市之間距離，現(xiàn)有一推銷員想從某一城市出發(fā)巡回經(jīng)過每一城市（且每城市只經(jīng)過一次），最后又回到出發(fā)點(diǎn)，問如何找一條最短路徑。窮舉法的時間復(fù)雜性為O(n!)n=21時，21!=5.11×1019,設(shè)每條路徑需CPU時間為1ns

，則總共要1620多年才能完成。2024/7/53

of158前言Asurveyofalgorithmicdesigntechniques.Abstractthinking.Howtodevelopnewalgorithmsforanyproblemthatmayarise.Beagreatthinkeranddesigner.Not:Alistofalgorithms-Learntheircode-Tracethemuntilwork-Implementthem-beamundaneprogrammer2024/7/54

of158前言：學(xué)習(xí)算法的意義

Story-1

Seriousdamagetoyourpositionwithinthecompany!!!“Ican’tfindanefficientalgorithm,IguessI’mjusttoodumb.”2024/7/55

of158前言：學(xué)習(xí)算法的意義

Story-2

“Ican’tfindanefficientalgorithm,becausenosuchalgorithmispossible!”Unfortunately,provingintractabilitycanbejustashardasfindingefficientalgorithms!!!

Nohope!!!P

NP2024/7/56

of158前言：學(xué)習(xí)算法的意義

Story-3

“Ican’tfindanefficientalgorithm,butneithercanallthesefamouspeople”2024/7/57

of158前言：學(xué)習(xí)算法的意義

Story-4

“Anyway,wehavetosolvethisproblem.Canwesatisfywithagoodsolution?“2024/7/58

of158

(1)

皇后問題:這是高斯1850年提出的一個著名問題：國際象棋中的“皇后”在橫向、直向、和斜向都能走步和吃子，問在n×n格的棋盤上如何能擺上n個皇后而使她們都不能互相攻擊。

一些有趣的問題設(shè)n=4，試一試。當(dāng)n很大時，問題很難。

對于n=8,現(xiàn)已知此問題

共有92種解，但只有12

種是獨(dú)立的，其余的都

可以由這12種利用對稱

或旋轉(zhuǎn)而得到。2024/7/59

of158(2)背包問題1：有一旅行者要從n種物品中選取不超過b千克重的行李隨身攜帶，要求總價值最大。例：設(shè)背包的容量為50千克。物品1重10千克，價值60元；物品2重20千克，價值100元；物品3重30千克，價值120元。求總價值最大。(3)背包問題2：有一商人要從n種貨物中選取不超過b千克重的行李隨身攜帶，要求總價值最大。例：設(shè)背包的容量為50千克。物品1有60千克，每千克價值60元；物品2有20千克，每千克價值100元；物品3有40千克，每千克價值120元。求總價值最大。2024/7/510

of158過橋問題(4)有4個人打算過橋，他們都在橋的某一端。時間是晚上，他們只有一只手電筒。最多只能有兩個人同時過橋，而且必須攜帶手電筒。必須步行將手電筒帶來帶去。每個人走路的速度不同：甲過橋需要1分鐘，乙2分鐘，丙5分鐘，丁10分鐘。兩個人一起走的速度等于其中較慢的人的速度。要求過橋總時間最短。2024/7/511

of158(5)有八種化學(xué)藥品A、B、C、D、W、X、Y、Z要裝箱運(yùn)輸。雖然量不大，僅裝1箱也裝不滿，但出于安全考慮，有些藥品不能同裝一箱。在下表中，符號“×”表示相應(yīng)的兩種藥品不能同裝一箱。運(yùn)輸這八種化學(xué)藥品至少需要裝

箱。

藥品裝箱問題2024/7/512

of1582024/7/513

of158（5）著色：北京地圖2024/7/514

of158著色問題就是對圖G

的每個頂點(diǎn)指定一種顏色,使鄰接的結(jié)點(diǎn)著不同的顏色.G

的著色數(shù)記為x(G)。結(jié)點(diǎn)著色2024/7/515

of158韋爾奇

鮑威爾法(WelchPowell)1)將圖G

中的結(jié)點(diǎn)按度數(shù)遞減的次序進(jìn)行排列(相同度數(shù)的結(jié)點(diǎn)的排列隨意)。2)用第一種顏色，對第一點(diǎn)著色，并按排列次序?qū)εc前面結(jié)點(diǎn)不相鄰的每一點(diǎn)著同樣的顏色。3)用第二種顏色對尚未著色的點(diǎn)重復(fù)第2步,直到所有的點(diǎn)都著上顏色為止。2024/7/516

of158例試用韋爾奇

鮑威爾法對圖進(jìn)行著色。按度數(shù)遞減次序排列各點(diǎn)CABFGHDE

第一種顏色：

第二種顏色：

第三種顏色:解：C,A,GB,H,D,EF所以圖是三色的。另外圖不能是兩色的,因?yàn)閳D中有A,B,F兩兩相鄰,所以x(G)=32024/7/517

of158Y、X、D、A、B、C、W、Z2024/7/518

of158前言（5）續(xù)已知研究生選課情況，安排課程考試的日程研究生選課情況表

姓名選修課1選修課2選修課3

楊一算法分析（A）形式語言（B）計(jì)算機(jī)網(wǎng)絡(luò)（E）

石磊計(jì)算機(jī)圖形學(xué)（C）模式識別（D）

魏濤計(jì)算機(jī)圖形學(xué)（C）計(jì)算機(jī)網(wǎng)絡(luò)（E）人工智能（F）

馬耀先模式識別（D）人工智能（F）算法分析（A）

齊硯生形式語言（B）人工智能（F）2024/7/519

of158

課程關(guān)系圖DEFCBA頂點(diǎn)：表示課程；

姓名選修課1選修課2選修課3

楊一算法分析（A）形式語言（B）計(jì)算機(jī)網(wǎng)絡(luò)（E）

石磊計(jì)算機(jī)圖形學(xué)（C）模式識別（D）

魏濤計(jì)算機(jī)圖形學(xué)（C）計(jì)算機(jī)網(wǎng)絡(luò)（E）人工智能（F）

馬耀先模式識別（D）人工智能（F）算法分析（A）

齊硯生形式語言（B）人工智能（F）邊：同一研究生選修的課程用邊連接----有邊連接的課程不能按排在同一時間考試；2024/7/520

of158◆課程考試按排問題轉(zhuǎn)化為圖的著色問題

--用盡可能少的顏色該圖的每個頂點(diǎn)著色，使相鄰的頂點(diǎn)著上不同的顏色；

---每一種顏色代表一個考試時間，著上相同顏色的頂點(diǎn)是可以安排在同一時間考試的課程；按頂點(diǎn)度數(shù)從大到小排列：FAECBD

F:藍(lán)色

;A,C:紅色；E,D:綠色；B:黃色；

即A,C可安排在同一時間考試，E,D可安排在同一時間考試;DEFCBAACEFBD2024/7/521

of158螞蟻問題（6）有一根10厘米的細(xì)木桿，在第2厘米、第4厘米、第5厘米、第8厘米、第9厘米這五個位置上各有一只螞蟻。木桿很細(xì)，不能同時通過一只螞蟻。開始時，螞蟻的頭朝左還是朝右是任意的，它們只能朝前走或調(diào)頭，但不會后退。所有螞蟻的速度都相同，均為1cm/s。當(dāng)任意兩只螞蟻碰頭時，兩只螞蟻會同時掉頭并且仍然按1cm/s朝相反方向走。求螞蟻掉下木桿的最小和最大時間。123456789abcde2024/7/522

of1585秒，a掉；6秒，e掉；8秒，b和d掉；9秒，c掉。1234567890.5s…3.5sabcdeabcde2024/7/523

of158本課程教材及主要參考書[1](教材)王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析(第3版)，電子工業(yè)出版社，2007

ISBN:978-7-121-04278-2

[2](教材)HarryR.Lewis.計(jì)算理論基礎(chǔ)(第2版),清華大學(xué)出版社,2006ISBN:7-302-13288-7[3](美)科曼(Cormen,T.H.）.潘金貴譯.算法導(dǎo)論(IntroductiontoAlgorithmsSecondEdition)，機(jī)械工業(yè)出版社，2006.9[4]MichaelSipser.IntroductiontotheTheoryofComputation[M].Thomson,secondedition,2006.2024/7/524

of158課程內(nèi)容數(shù)學(xué)基礎(chǔ)、遞歸與分治、動態(tài)規(guī)劃、貪心法、回溯法、分支限界法、概率算法、線性規(guī)劃與網(wǎng)絡(luò)流、計(jì)算理論基礎(chǔ)（集合關(guān)系與語言、有窮自動機(jī)、圖靈機(jī)、不可判定性、計(jì)算復(fù)雜性、NP完全性）、近似算法等.課程安排

56學(xué)時成績平時成績30％，期末閉卷成績70％CH1算法概述2024/7/526

of158一、算法設(shè)計(jì)與分析的研究對象非數(shù)值問題二、什么是算法例1已知兩正整數(shù)m和n，求二者的最大公因子算法1.1歐幾里德(Euclid)算法輸入正整數(shù)m,n輸出m和n的最大公因子

算法概述2024/7/527

of158定理對任意正整數(shù)m和任意非負(fù)整數(shù)n，并且m>n≥0

有g(shù)cd(m,n)=gcd(n,mmodn)

如gcd(24,18)=gcd(18,6)=gcd(6,0)=62024/7/528

of158整除的基本性質(zhì)若a|b且a|c,則對任意的整數(shù)m,n,有a|(bm+cn).證明因?yàn)閍|b且a|c,故b=aq1和c=aq2.于是,

bm+cn=a(q1m+q2n),

所以,a|(bm+cn).2024/7/529

of158最大公約數(shù)（最大公因子）定理

設(shè)a和b都是正整數(shù),且a>b,

a=bq+r0<r<b

其中q和r都是正整數(shù).則:①a和b的任一公約數(shù)也是b和r的公約數(shù)；

②b和r的任一公約數(shù)也是a和b的公約數(shù)；

③(a,b)=(b,r);2024/7/530

of158a=bq+r

①a和b的公約數(shù)也是b和r的公約數(shù)；證明①若d|a且d|b,則d|(a-bq)即d|r.這即表明:若d是a和b的公約數(shù),d必是b和r的公約數(shù).②若d|b且d|r,則:d|(bq＋r)即d|a.這即是說若d是b和r的公約數(shù),d也必是a和b的公約數(shù).2024/7/531

of158S1求余數(shù):m除以n,令r是所得的余數(shù)，轉(zhuǎn)S2S2判斷余數(shù):若r=0,則輸出n的當(dāng)前值，算法結(jié)束，否則轉(zhuǎn)S3S3代替:m←n,n←r,轉(zhuǎn)S12024/7/532

of158算法的五個特征1）有窮性2）確定性3）輸入4）輸出5）可行性算法的定義:Informally,analgorithmisanywell-definedcomputationalprocedurethattakessomevalue,orsetofvalues,asinputandproducessomevalue,orsetofvalues,asoutput.Analgorithmisthusasequenceofcomputationalstepsthattransformtheinputintotheoutput.

2024/7/533

of158評價算法的標(biāo)準(zhǔn)1）算法執(zhí)行的時間短（時間復(fù)雜性）2）算法需要的存儲空間小（空間復(fù)雜性）3）正確性

4）可讀性5）最優(yōu)性2024/7/534

of158算法的時間復(fù)雜性：處理一個問題規(guī)模為n的輸入，算法所需要的執(zhí)行次數(shù)（或執(zhí)行的步數(shù)），記為T(n)算法的空間復(fù)雜性：處理一個問題規(guī)模為n的輸入，算法所需要的空間數(shù)，記為S(n)2024/7/535

of158例:雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、母、雛各幾何？

a+b+c=1005a+3b+c/3=100cmod3=02024/7/536

of158k=0;for(a=0;a<=n;a++){for(b=0;b<=n;b++){for(c=0;c<=n;c++){if((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)){

g[k]=a;//k為解的個數(shù)，如第1組解為g[1]=10,…

m[k]=b;

s[k]=c;k++;}

}}}

a+b+c=1005a+3b+c/3=100cmod3=0內(nèi)循環(huán)的循環(huán)體執(zhí)行(n+1)(n+1)(n+1)=n3+3n2+3n+12024/7/537

of158算法改進(jìn)k=0;for(a=0;a<=n/5;a++){for(b=0;b<=n/3;b++){

c=n–a–b;if((5*a+3*b+c/3==n)&&(c%3==0)){

g[k]=a;

m[k]=b;

s[k]=c;k++;}

}}}

a+b+c=n5a+3b+c/3=ncmod3=0內(nèi)循環(huán)的循環(huán)體執(zhí)行(n/5+1)(n/3+1)=n2/15

+8n/15+12024/7/538

of158O、o、

、

、

第一種理解方法設(shè)f和g是定義域?yàn)樽匀粩?shù)N上的函數(shù)f(n)=O(g(n)).

若存在正數(shù)c和n0使得對一切n

n0

有0f(n)cg(n)f(n)=(g(n)).

若存在正數(shù)c和n0使得對一切n

n0有0cg(n)f(n)f(n)=o(g(n)).

若對任意正數(shù)c存在n0使得對一切n

n0有0f(n)<cg(n)f(n)=(g(n)).

若對任意正數(shù)c存在n0使得對一切n

n0有0cg(n)<f(n)f(n)=(g(n))

f(n)=O(g(n))且f(n)=(g(n))2024/7/539

of158O、o的區(qū)別設(shè)f和g是定義域?yàn)樽匀粩?shù)N上的函數(shù)f(n)=O(g(n)).

若存在正數(shù)c和n0使得對一切n

n0

有

0f(n)cg(n)f(n)=o(g(n)).

若對任意正數(shù)c存在n0使得對一切n

n0有0f(n)<cg(n)O(g(n))是對某個常數(shù)c>0成立;

o(g(n))是對所有常數(shù)c>0成立.2024/7/540

of158O、o、

、

、

第二種理解方法求復(fù)雜性函數(shù)階的極限方法例如，f(n)=n2/4,g(n)=n2,則n2/4=θ(n2)f(n)=logn,g(n)=n,則logn=o(n)o

2024/7/541

of158f(n)c0g(n)c1g(n)n0f(n)is

(g(n))

f(n)cg(n)n0f(n)isO(g(n))

f(n)cg(n)n0f(n)is

(g(n))

2024/7/542

of158例1：等式0.75n2=O(n)何時成立？等式3n1/2=O(n)在n=9時成立嗎？永不成立n=9時，雖然兩邊看似值相等，

但等式不成立2024/7/543

of158例2：60n2+5n+160n2+5n+1≤60n2+5n2+n2=66n2

對于n

≥1

所以60n2+5n+1=O(n2)

又60n2+5n+1≥60n2

對于n

≥1

所以60n2+5n+1=Ω(n2)綜上60n2+5n+1=Θ(n2)2024/7/544

of158例3：1+2+…+n

1+2+…+n

≤n+n+…+n=n2

對于n

≥1

所以

1+2+…+n=O(n2)

又1+2+…+n

≥1+1+…+1=n

對于n

≥1

所以1+2+…+n=Ω(n)綜上1+2+…+n=?2024/7/545

of158法1又1+2+…+n

≥

2024/7/546

of158法2:分割求和為方便起見,設(shè)n為偶數(shù),則

2024/7/547

of158

所以1+2+…+n=Ω(n2)綜上1+2+…+n=Θ(n2)練習(xí)：

1、給出1k+2k+…+nk

的Θ表示

2、給出logn!的Θ表示

1、1k+2k+…+nk=Θ(nk+1)2、logn!=Θ(nlog

n)2024/7/548

of158標(biāo)準(zhǔn)復(fù)雜性函數(shù)的比較

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)注意：1）不能劃等號2）以下若無特殊聲明，log是以2為底的對數(shù)3）上式只有在n較大的時候成立O(1)的含義？計(jì)算時間由一個常數(shù)（零次多項(xiàng)式）來限界多項(xiàng)式時間階指數(shù)時間階2024/7/549

of158指數(shù)時間一個算法的時間復(fù)雜性如果是O(2n)，則稱此算法需要指數(shù)時間。多項(xiàng)式時間一個算法的時間復(fù)雜性如果是O(nk)(k為有理數(shù)），則稱此算法需要多項(xiàng)式時間。有效算法以多項(xiàng)式時間為限界的算法稱為有效算法。2024/7/550

of158TimetoFinishInputSize(n)O(nx)O(n)O(1)O(n

lg

n)O(an)2024/7/551

of158例例：算法A1,A2的時間復(fù)雜性分別是n,2n,設(shè)100μs是一個單位時間，求A1,A2在1s內(nèi)能處理的問題規(guī)模。已知lg2=0.301T(n)=nT(n)*10-4=1即n*10-4=1所以n=

104

2024/7/552

of158時間復(fù)雜性函數(shù)問題規(guī)模102030405060n10－52*10－53*10-54*10-55*10-56*10-5n210-44*10-49*10-416*10-425*10-436*10-4n310-38*10-327*10-364*10-3125*10-3216*10-3n510-13.224.31.7分5.2分13.0分2n.001秒1.0秒17.9分12.7天35.7年366世紀(jì)3n.059秒58分6.5年3855世紀(jì)2*108世紀(jì)1.3*1013世紀(jì)2024/7/553

of158

時間復(fù)雜性函數(shù)1小時可解的問題實(shí)例的最大規(guī)模計(jì)算機(jī)快100倍的計(jì)算機(jī)快1000倍的計(jì)算機(jī)nN1100N11000N1n2N210N231.6N2n3N34.64N310N3n5N42.5N43.98N42nN5N5+6.64N5+9.973nN6N6+4.19N6+6.292024/7/554

of158課堂練習(xí)假設(shè)某算法在輸入規(guī)模為n的時間復(fù)雜性為T(n)=3*2n。在某臺計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時間為t秒?，F(xiàn)在另一計(jì)算機(jī)，其運(yùn)行速度為第一臺的64倍，那么在這臺新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問題？2024/7/555

of158課堂練習(xí)解：設(shè)新機(jī)器用同一算法內(nèi)能解輸入規(guī)模為n1的問題，那么有3*2n=3*2n1/64，解得n1=n+6.數(shù)學(xué)符號2024/7/557

of158符號一、符號說明1．取整函數(shù)

x

：小于等于x的最大整數(shù)

x

：大于等于x的最小整數(shù)性質(zhì)

x-1<x

x

x

<x+12024/7/558

of158符號2024/7/559

of158符號

a/b

[a+(b-1)]/b

a/b

[a-(b-1)]/b2024/7/560

of158符號鴿巢原理（又名抽屜原理）

若n+1只鴿子飛入n個鴿巢，那么至少有一個鴿巢至少有2只鴿子.

若n只鴿子飛入m(n>m)個鴿巢，那么至少有一個鴿巢至少有

(n-1)/m+1只鴿子.2024/7/561

of158Halloweentreats

EveryyearthereisthesameproblematHalloween:Eachneighborisonlywillingtogiveacertaintotalnumberofsweetsonthatday,nomatterhowmanychildrencallonhim,soitmayhappenthatachildwillgetnothingifitistoolate.Toavoidconflicts,thechildrenhavedecidedtheywillputallsweetstogetherandthendividethemevenlyamongthemselves.Fromlastyear'sexperienceofHalloweentheyknowhowmanysweetstheygetfromeachneighbor.Sincetheycaremoreaboutjusticethanaboutthenumberofsweetstheyget,theywanttoselectasubsetoftheneighborstovisit,sothatinsharingeverychildreceivesthesamenumberofsweets.Theywillnotbesatisfiediftheyhaveanysweetsleftwhichcannotbedivided.

2024/7/562

of158SampleInput45(thenumberofchildrenandthenumberofneighbors,respectively.)123753671125131700SampleOutput35234Halloweentreats

2024/7/563

of158符號2對數(shù)

lg2=0.3012024/7/564

of158符號證明：2024/7/565

of158符號logb

N=loga

N/logablogeN=lnN

e=2.71828logab=1/logba2024/7/566

of158符號二、階乘

n!=o(nn)

n!=

(2n)logn!=(nlogn)2024/7/567

of158符號三、求和等比級數(shù)的求和公式2024/7/568

of158符號調(diào)和級數(shù)2024/7/569

of158利用積分2024/7/570

of1582024/7/571

of158遞歸式方法一:特征方程法2024/7/574

of158斐波那契數(shù)遞歸方程及其求解定義：給定一個數(shù)的序列T(0),T(1),…,

T(n),…,把T(n)和某些T(i)(0≤i<n)聯(lián)系起來的一個等式就叫做一個遞歸關(guān)系。如果一對大兔子每月能生一對小兔，而每對小兔