算法設(shè)計(jì)-第一章

計(jì)算機(jī)算法設(shè)計(jì)與分析（第3版）王曉東編著電子工業(yè)出版社算法設(shè)計(jì)與分析引論1．關(guān)于用計(jì)算機(jī)解決問(wèn)題1.1計(jì)算機(jī)的能力電子計(jì)算機(jī)的出現(xiàn)是本世紀(jì)的一件大事，因?yàn)樗淖兞宋覀冞@個(gè)世界的面貌?？梢院敛豢鋸埖剡@么說(shuō)，今天人們依賴(lài)于計(jì)算機(jī)，就象人們依賴(lài)于電力，如果它暫停了，社會(huì)就無(wú)法運(yùn)轉(zhuǎn)?？焖匐娮佑?jì)算機(jī)貴在神速，也就是它的運(yùn)算速度快，同時(shí)它的發(fā)展之迅速也是驚人的。從每秒5000次運(yùn)算，發(fā)展到現(xiàn)在的運(yùn)算速度每秒數(shù)千億次運(yùn)算。元器件從繼電器、真空管、晶體管、集成電路、大規(guī)模集成電路，發(fā)展到超大規(guī)模集成電路。結(jié)構(gòu)上從每臺(tái)機(jī)器作為運(yùn)算工具的“單兵作戰(zhàn)”模式，發(fā)展到今天將范圍遍及各大洲的計(jì)算機(jī)網(wǎng)絡(luò)，算法也從單機(jī)的串行計(jì)算發(fā)展到網(wǎng)絡(luò)上并行的分布計(jì)算。一臺(tái)作109次/秒運(yùn)算（1G）的計(jì)算機(jī)的效率超過(guò)10億人同時(shí)工作。它可以作中期的天氣預(yù)報(bào)，可以控制龐大的化工廠(chǎng)生產(chǎn)過(guò)程，以至于還可以駕馭現(xiàn)代化戰(zhàn)爭(zhēng)，從這個(gè)意義上來(lái)說(shuō)它確實(shí)是近乎神奇的。不過(guò)必須強(qiáng)調(diào)的是這些都是在人的安排下進(jìn)行工作的。比如人們利用計(jì)算機(jī)作天氣預(yù)報(bào)，必須依據(jù)天氣變化規(guī)律，作出它的偏微分方程數(shù)學(xué)模型，以及編好程序，指導(dǎo)計(jì)算機(jī)按照人的安排一步步地工作，計(jì)算預(yù)報(bào)數(shù)據(jù)，繪制氣象云圖。這就是說(shuō)，計(jì)算機(jī)雖然神通廣大，還是在人的控制下工作。同時(shí)還應(yīng)說(shuō)明計(jì)算機(jī)并非什么都能做，有的事情理論上它根本做不了。討論哪些事計(jì)算機(jī)能做，哪些事計(jì)算機(jī)做不了，屬于可計(jì)算性理論研究的范疇。還有一些問(wèn)題理論上計(jì)算機(jī)雖是能做，但實(shí)際上又是不可能完成的。比如拿最簡(jiǎn)單例子，26個(gè)英文字母全排列，它的排列數(shù)為：26！≈4×1026以每年365天計(jì)算，共有365×24×3600＝3.1536×107秒以每秒能完成107個(gè)排列的超高速電子計(jì)算機(jī)來(lái)做這項(xiàng)工作，需要4×1026/(3.1536×1014)≈1.2×1012年即使計(jì)算機(jī)運(yùn)行速度隨著技術(shù)的提高，恐怕也還是不可能實(shí)現(xiàn)的。因此計(jì)算機(jī)的速度再提高也有它的極限。1.2用計(jì)算機(jī)解決問(wèn)題的關(guān)鍵任何一項(xiàng)計(jì)算，總要事先擬定計(jì)算方案和規(guī)劃計(jì)算步驟。為使計(jì)算機(jī)的計(jì)算過(guò)程能夠解決某一問(wèn)題，必須為計(jì)算機(jī)設(shè)計(jì)執(zhí)行的解決方案中的每個(gè)詳細(xì)步驟，并且將此過(guò)程完整地描述出來(lái)。所謂算法是對(duì)某個(gè)問(wèn)題求解方案的完整而明確的描述。與算法有關(guān)的還有一個(gè)大家熟悉的公式：

程序=算法十?dāng)?shù)據(jù)結(jié)構(gòu)也就是說(shuō)，算法設(shè)計(jì)和程序設(shè)計(jì)是不完全相同的。由于數(shù)字計(jì)算機(jī)運(yùn)算速度很高，是人工手算所不能比擬的。為了充分發(fā)揮計(jì)算機(jī)的這種優(yōu)點(diǎn)，在用計(jì)算機(jī)求解問(wèn)題過(guò)程中，應(yīng)盡量減少人工干預(yù)。因此，必須先將所制定的解決方案“告訴”計(jì)算機(jī)，使計(jì)算機(jī)按照人們規(guī)定的計(jì)算順序去自動(dòng)執(zhí)行。用計(jì)算機(jī)能接受的“語(yǔ)言”來(lái)描述解題步驟，這項(xiàng)工作叫做程序設(shè)計(jì)，它還包含了需要使用合適的數(shù)據(jù)結(jié)構(gòu)?！八惴ㄔO(shè)計(jì)與分析”是研究算法的一門(mén)學(xué)科。它還很年輕遠(yuǎn)未定型，還處在發(fā)展中。有人說(shuō)“計(jì)算機(jī)科學(xué)是一門(mén)研究算法的科學(xué)”。不論這個(gè)說(shuō)法是否全面，算法無(wú)疑是計(jì)算機(jī)科學(xué)的重要組成部分。它近來(lái)發(fā)展極其迅速?！八惴ㄔO(shè)計(jì)與分析”已是計(jì)算機(jī)專(zhuān)業(yè)本科生的一門(mén)必需掌握的內(nèi)容。1.3一些有趣的問(wèn)題(1)巡回推銷(xiāo)員問(wèn)題:設(shè)有n個(gè)城市，已知任意兩城市間之距離，現(xiàn)有一推銷(xiāo)員想從某一城市出發(fā)巡回經(jīng)過(guò)每一城市（且每城市只經(jīng)過(guò)一次），最后又回到出發(fā)點(diǎn)，問(wèn)如何找一條最短路徑。設(shè)距離矩陣如下：試一試求出最短路徑。úúúúúú?ùêêêêêê?é=0186572641805673556556041772734103964557390D（2)皇后問(wèn)題:這是高斯1850年提出的一個(gè)著名問(wèn)題：國(guó)際象棋中的“皇后”在橫向、直向、和斜向都能走步和吃子，問(wèn)在n×n格的棋盤(pán)上如何能擺上n個(gè)皇后而使她們都不能互相吃。當(dāng)n很大時(shí)，問(wèn)題很難。對(duì)于n=8,現(xiàn)已知此問(wèn)題共有92種解，但只有12種是獨(dú)立的，其余的都可以由這12種利用對(duì)稱(chēng)性或旋轉(zhuǎn)而得到。設(shè)n=4，試一試。

(3）設(shè)天平有一些25克的砝碼，一些10克的砝碼，一些5克的砝碼和一些1克的砝碼?，F(xiàn)要稱(chēng)63克的物體，問(wèn)至少需要用幾個(gè)砝碼。

(4）背包問(wèn)題1：有一旅行者要從n種物品中選取不超過(guò)b公斤重的行李隨身攜帶，要求總價(jià)值最大。例：設(shè)背包的容量為50千克。物品1重10千克，價(jià)值60元；物品2重20千克，價(jià)值100元；物品3重30千克，價(jià)值120元。求總價(jià)值最大。（5）背包問(wèn)題2：設(shè)有n=8個(gè)體積分別為54，45，43，29，23，21，14，1的物體和一個(gè)容積為C=110的背包，問(wèn)選擇哪幾個(gè)物體裝入背包可以使其裝的最滿(mǎn)。

（6）裝箱問(wèn)題：設(shè)有體積分別為v1,v2,…,vn的n種物品u1,u2,…,un裝到容量為L(zhǎng)的箱子里。不同的裝箱方案所需的箱子數(shù)目可能不同，問(wèn)如何裝箱能裝完這n種物品且使用的箱子數(shù)目最少。

（7）平面圖的四色猜想問(wèn)題：一個(gè)平面圖是否用四種顏色就可使相鄰的區(qū)域顏色都不相同？2.算法設(shè)計(jì)的重要性算法是計(jì)算機(jī)科學(xué)的靈魂美國(guó)計(jì)算機(jī)科學(xué)家唐納德·克努斯(DonaldKnuth,中文名：高德納

)

經(jīng)典巨著《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)

》，第一卷《《基本算法》，獲得圖靈獎(jiǎng)。比爾·蓋茨曾經(jīng)花了幾個(gè)月的時(shí)間讀完這一卷，并且做了大量的練習(xí)，然后他說(shuō)，如果你想成為一個(gè)優(yōu)秀的程序員，那就去讀這個(gè)《基本算法》吧。高德納本人的說(shuō)法更犀利：要是看不懂，就別當(dāng)程序員。ACM’sTuringAwards1966年至1999年的圖靈獎(jiǎng)獲得者中有12人直接或間接地與算法相關(guān)：D.E.Knuth,M.O.RabinandD.S.Scott,R.W.Floyd,C.A.R.Hoare,S.A.Cook,N.Wirth,R.M.Karp,J.E.HopcrftandR.E.Steams,M.Blum,etc.二十世紀(jì)算法的三大發(fā)現(xiàn)：快速傅里葉變換：使數(shù)字信號(hào)處理、數(shù)字通信等技術(shù)成為現(xiàn)實(shí)最短路徑算法：在許多領(lǐng)域尤其是計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域起重要作用距陣乘法：打破了距陣相乘的O(n3)的界限3.課程信息:GoalAsurveyofalgorithmicdesigntechniques.Abstractthinking.Howtodevelopnewalgorithmsforanyproblemthatmayarise.Beagreatthinkeranddesigner.Not:Alistofalgorithms-Learntheircode-Tracethemuntilwork-Implimentthem-beamundaneprogrammer培養(yǎng)良好的軟件開(kāi)發(fā)習(xí)慣，即在軟件開(kāi)發(fā)過(guò)程中要考慮：能不能解決這個(gè)問(wèn)題？一個(gè)算法有多好?還能更好嗎?4.課程內(nèi)容:介紹計(jì)算機(jī)應(yīng)用領(lǐng)域提出的一些算法和計(jì)算復(fù)雜性的基本原理。先修課程：數(shù)據(jù)結(jié)構(gòu)，c或c++編程主要內(nèi)容：第一章算法概述第二章遞歸與分治策略第三章動(dòng)態(tài)規(guī)劃第四章貪心算法第五章回溯法第六章分支限界法5.參考教材1.計(jì)算機(jī)算法設(shè)計(jì)與分析（第三版），電子工業(yè)出版社，2007，王曉東2.《算法設(shè)計(jì)技巧與分析》，電子工業(yè)出版社，2004.3.計(jì)算機(jī)算法基礎(chǔ)（第二版），余祥宣、崔國(guó)華、鄒海明，華中科技大學(xué)出版社，2002.14.算法設(shè)計(jì)與分析基礎(chǔ)（第二版），清華大學(xué)出版社，萊維丁著，潘彥譯第1章算法概述學(xué)習(xí)要點(diǎn):理解算法的概念。理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。掌握算法的計(jì)算復(fù)雜性概念。掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。掌握用C++語(yǔ)言描述算法的方法。1.1算法與程序算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。算法是若干指令的有窮序列，滿(mǎn)足性質(zhì)：(1)輸入：有外部提供的量作為算法的輸入。(2)輸出：算法產(chǎn)生至少一個(gè)量作為輸出。(3)確定性：組成算法的每條指令是清晰，無(wú)歧義的。(4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。(5)可行性：算法(Algorithm)程序(Program)程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不滿(mǎn)足算法的性質(zhì)(4)。例如操作系統(tǒng)，是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問(wèn)題，每一個(gè)問(wèn)題由操作系統(tǒng)中的一個(gè)子程序通過(guò)特定的算法來(lái)實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。問(wèn)題求解(ProblemSolving)證明正確性分析算法設(shè)計(jì)程序理解問(wèn)題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法正確性定義：在給定有效輸入后，算法經(jīng)過(guò)有限時(shí)間的計(jì)算并產(chǎn)生正確的答案，就稱(chēng)算法是正確的。正確性證明的內(nèi)容：方法的正確性證明——算法思路的正確性。證明一系列與算法的工作對(duì)象有關(guān)的引理、定理以及公式。程序的正確性證明——證明所給出的一系列指令確實(shí)做了所要求的工作。程序正確性證明的方法：大型程序的正確性證明——可以將它分解為小的相互獨(dú)立的互不相交的模塊，分別驗(yàn)證。小模塊程序可以使用以下方法驗(yàn)證：數(shù)學(xué)歸納法、軟件形式方法等。衡量算法性能一般有下面幾個(gè)標(biāo)準(zhǔn)2.易讀性3.健壯性4.算法的時(shí)間和空間性能：高效率和低存儲(chǔ)空間1.2算法分析(AlgorithmAnalysis)算法分析：對(duì)于算法的時(shí)間和空間復(fù)雜度進(jìn)行定量分析。分析算法時(shí)間復(fù)雜度的基本步驟算法時(shí)間復(fù)雜度的有關(guān)概念分析、求解算法復(fù)雜度的基本方法算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱(chēng)為時(shí)間復(fù)雜性，需要的空間資源的量稱(chēng)為空間復(fù)雜性。這個(gè)量應(yīng)該只依賴(lài)于算法要解的問(wèn)題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問(wèn)題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。一般把時(shí)間復(fù)雜性和空間復(fù)雜性分開(kāi)，并分別用T和S來(lái)表示，則有：T=T(N,I)和S=S(N,I)。（通常，讓A隱含在復(fù)雜性函數(shù)名當(dāng)中）算法復(fù)雜性分析

算法復(fù)雜性=算法所需要的計(jì)算機(jī)資源算法的時(shí)間復(fù)雜性T(n)；算法的空間復(fù)雜性S(n)。其中n是問(wèn)題的規(guī)模（輸入大?。?。1.空間復(fù)雜性分析兩種占用：存儲(chǔ)程序和輸入數(shù)據(jù)的空間存儲(chǔ)中間結(jié)果或操作單元所占用空間——額外空間影響空間的主要因素：存儲(chǔ)程序的空間一般是常數(shù)(和輸入規(guī)模無(wú)關(guān))輸入數(shù)據(jù)空間為輸入規(guī)模O(n)空間復(fù)雜性考慮的是額外空間的大小如果額外空間相對(duì)于輸入規(guī)模是常數(shù)，稱(chēng)為原地工作的算法。2.時(shí)間復(fù)雜性分析計(jì)量工作量的標(biāo)準(zhǔn):對(duì)于給定問(wèn)題，該算法所執(zhí)行的基本運(yùn)算的次數(shù)。通常用漸進(jìn)形式表示比如，T(n)=Ο(n2)、Ω

(n2)或θ(n2)基本運(yùn)算的選擇：根據(jù)問(wèn)題選擇適當(dāng)?shù)幕具\(yùn)算。問(wèn)題基本運(yùn)算在表中查找x比較實(shí)矩陣相乘實(shí)數(shù)乘法排序比較遍歷二叉樹(shù)置指針3.分析時(shí)間復(fù)雜度的基本步驟一、選取一種運(yùn)算作為基本運(yùn)算二、表示出在算法運(yùn)行期間基本運(yùn)算執(zhí)行的總頻數(shù)三、漸近時(shí)間復(fù)雜度（asymptotictimecomplexity）函數(shù)的漸進(jìn)性態(tài)與漸進(jìn)表達(dá)式：一般來(lái)說(shuō)，當(dāng)N單調(diào)增加且趨于∞時(shí)，T(N)也將單調(diào)增加趨于∞。對(duì)于T(N)，如果存在函數(shù)T'(N)，使得當(dāng)N→∞使有(T(N)-T'(N))/T(N)→0，那么我們就說(shuō)T'(N)是T(N)當(dāng)N→∞時(shí)的漸進(jìn)性態(tài)。在數(shù)學(xué)上，T'(N)是T(N)當(dāng)N→∞時(shí)的漸進(jìn)表達(dá)式。例如：3N2+4NlogN+7與3N2。算法漸近復(fù)雜性T(n)

,asn

;(T(n)-t(n))/T(n)0，asn;t(n)是T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。在數(shù)學(xué)上，t(n)是T(n)的漸近表達(dá)式，是T(n)略去低階項(xiàng)留下的主項(xiàng)。它比T(n)簡(jiǎn)單。算法復(fù)雜性分析算法復(fù)雜性在漸近意義下的階：漸近意義下的記號(hào)：O、Ω、θ、o

設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。O的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N

N0時(shí)有f(N)Cg(N)，則稱(chēng)函數(shù)f(N)當(dāng)N充分大時(shí)上有界，且g(N)是它的一個(gè)上界，記為f(N)=O(g(N))。即f(N)的階不高于g(N)的階。根據(jù)O的定義，容易證明它有如下運(yùn)算規(guī)則：(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)如果g(N)=O(f(N))，則O(f)+O(g)=O(f)；(5)O(Cf(N))=O(f(N))，其中C是一個(gè)正的常數(shù)；(6)f=O(f)。

規(guī)則Ｏ(f(n))+Ｏ(g(n))=Ｏ(max{f(n),g(n)})的證明：對(duì)于任意f1(n)∈Ｏ(f(n))，存在正常數(shù)c1和自然數(shù)n1，使得對(duì)所有n≥n1，有f1(n)≤c1f(n)。類(lèi)似地，對(duì)于任意g1(n)∈Ｏ(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對(duì)所有n≥n2，有g(shù)1(n)≤c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對(duì)所有的n≥n3，有f1(n)+g1(n)≤c1f(n)+c2g(n)≤c3f(n)+c3g(n)=c3(f(n)+g(n))≤c32max{f(n),g(n)}＝2c3h(n)＝Ｏ(max{f(n),g(n)}).算法復(fù)雜性分析Ω的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N

N0時(shí)有f(N)Cg(N)，則稱(chēng)函數(shù)f(N)當(dāng)N充分大時(shí)下有界，且g(N)是它的一個(gè)下界，記為f(N)=Ω(g(N))。即f(N)的階不低于g(N)的階。θ的定義：定義f(N)=θ(g(N))當(dāng)且僅當(dāng)f(N)=O(g(N))且f(N)=Ω(g(N))。此時(shí)稱(chēng)f(N)與g(N)同階。o的定義：對(duì)于任意給定的ε＞0，都存在正整數(shù)N0，使得當(dāng)N

N0時(shí)有f(N)/Cg(N)

ε,則稱(chēng)函數(shù)f(N)當(dāng)N充分大時(shí)的階比g(N)低，記為f(N)=o(g(N))。例如，4NlogN+7=o(3N2+4NlogN+7)。

漸近分析記號(hào)的若干性質(zhì)（1）傳遞性：f(n)=θ(g(n))，g(n)=θ(h(n))→f(n)=θ(h(n))；f(n)=Ｏ(g(n))，g(n)=Ｏ(h(n))→f(n)=Ｏ(h(n))；f(n)=Ω(g(n))，g(n)=Ω(h(n))→f(n)=Ω(h(n))；f(n)=ｏ(g(n))，g(n)=ｏ(h(n))→f(n)=ｏ(h(n))；f(n)=ω(g(n))，g(n)=ω(h(n))→f(n)=ω(h(n))；（2）反身性：f(n)=θ(f(n))；f(n)=Ｏ(f(n))；f(n)=Ω(f(n)).（3）對(duì)稱(chēng)性：f(n)=θ(g(n))<==>g(n)=θ(f(n)).（4）互對(duì)稱(chēng)性：f(n)=Ｏ(g(n))<==>g(n)=Ω(f(n))；f(n)=ｏ(g(n))<==>g(n)=ω(f(n))；（5）算術(shù)運(yùn)算：Ｏ(f(n))+Ｏ(g(n))=Ｏ(max{f(n),g(n)})；Ｏ(f(n))+Ｏ(g(n))=Ｏ(f(n)+g(n))；Ｏ(f(n))*Ｏ(g(n))=Ｏ(f(n)*g(n))；Ｏ(cf(n))=Ｏ(f(n))；g(n)=Ｏ(f(n))→Ｏ(f(n))+Ｏ(g(n))=Ｏ(f(n))。漸近表示—Examples[例1]設(shè)f(n)=10n2+20n。則有f(n)=O(n2)f(n)=Ω(n2)f(n)=θ(n2)[例2]設(shè)f(n)=aknk+ak-1nk-1+…+a1n+a0,(ak>0)。則有f(n)=O(nk)f(n)=

Ω

(nk)：f(n)=θ

(nk)由此可見(jiàn)，復(fù)雜度的漸近表示可以簡(jiǎn)潔地表示出復(fù)雜度的數(shù)量級(jí)別。對(duì)于算法的時(shí)間復(fù)雜度，通常從分平均、最壞、最好幾種情形來(lái)衡量，尤其是前兩種。算法的平均復(fù)雜性算法的最壞復(fù)雜性算法的最好復(fù)雜性算法的時(shí)間復(fù)雜性的有關(guān)概念（1）最壞情況下的時(shí)間復(fù)雜性Tmax(n)=max{T(I)|size(I)=n}（2）最好情況下的時(shí)間復(fù)雜性Tmin(n)=min{T(I)|size(I)=n}（3）平均情況下的時(shí)間復(fù)雜性Tavg(n)=其中I是問(wèn)題的規(guī)模為n的實(shí)例，p(I)是實(shí)例I出現(xiàn)的概率。[例1]檢索問(wèn)題的順序查找算法以元素的比較作為基本操作?？紤]成功檢索的情況。最好情況下的時(shí)間復(fù)雜度：θ

(1)最壞情況下的時(shí)間復(fù)雜度：θ

(n)在等概率前提下，平均情況下的時(shí)間復(fù)雜度：θ

(n)[例2]直