算法算法概述詳解PPT課件

1、1l 課時(shí)數(shù)：48節(jié)l 上課：1-16周l 成績(jī)：卷面成績(jī)（70%）+平時(shí)成績(jī)（30%）l 教材：計(jì)算機(jī)算法設(shè)計(jì)與分析, 王曉東,電子工業(yè)出版社, 2012l參考書(shū)： (1) 算法設(shè)計(jì)與分析, 鄭宗漢, 鄭曉明, 清華大學(xué)出版社 (2) 算法導(dǎo)論, Thomas H. Cormen編著. 潘金貴等譯, 機(jī)械工業(yè)出版社第1頁(yè)/共47頁(yè)22主要內(nèi)容介紹 第1 1章 算法概述 第2 2章 遞歸與分治策略 第3 3章 動(dòng)態(tài)規(guī)劃 第4 4章 貪心算法 第5 5章 回溯法 第6 6章 分支限界法第2頁(yè)/共47頁(yè)33意念與現(xiàn)實(shí)意念與現(xiàn)實(shí)(1): 一個(gè)例子一個(gè)例子給你一個(gè)無(wú)限容積的罐子和無(wú)限個(gè)球，球從1開(kāi)始連

2、續(xù)編號(hào) 在差在差1分鐘到零點(diǎn)時(shí)：將標(biāo)號(hào)為分鐘到零點(diǎn)時(shí)：將標(biāo)號(hào)為110的的10個(gè)球放進(jìn)罐子，個(gè)球放進(jìn)罐子，然后將然后將10號(hào)球從罐子里拿出。號(hào)球從罐子里拿出。 在差在差1/2分鐘到零點(diǎn)時(shí)：將標(biāo)號(hào)為分鐘到零點(diǎn)時(shí)：將標(biāo)號(hào)為1120的的10個(gè)球放進(jìn)罐個(gè)球放進(jìn)罐子，然后將子，然后將20號(hào)球從罐子里拿出。號(hào)球從罐子里拿出。 在差在差1/4分鐘到零點(diǎn)時(shí)：將標(biāo)號(hào)為分鐘到零點(diǎn)時(shí)：將標(biāo)號(hào)為2130的的10個(gè)球放進(jìn)罐個(gè)球放進(jìn)罐子，然后將子，然后將30號(hào)球從罐子里拿出。號(hào)球從罐子里拿出。 就這樣將游戲進(jìn)行下去。假定放球和取球不占時(shí)間，請(qǐng)問(wèn)，當(dāng)時(shí)鐘指向零點(diǎn)時(shí)，罐子里還剩多少個(gè)球？第3頁(yè)/共47頁(yè)44意念與現(xiàn)實(shí)意念與現(xiàn)實(shí)

3、(2): 一個(gè)例子一個(gè)例子這個(gè)答案很直接：無(wú)窮多個(gè)球無(wú)窮多個(gè)球！所有編號(hào)不是10n（n1）的球在放進(jìn)罐子里后就不會(huì)再拿出來(lái)；而在到達(dá)零點(diǎn)之前這種放球、取球的次數(shù)是無(wú)限的。因此，罐子里面的球在零點(diǎn)時(shí)將是無(wú)數(shù)個(gè)。你很確信這個(gè)答案嗎？你很確信這個(gè)答案嗎？ 現(xiàn)在來(lái)讓我們改變拿球的方式，將每次拿10、20、30號(hào)球分別變?yōu)槟?、2、3號(hào)球，即第x次拿球，所拿出來(lái)的球的編號(hào)是x。結(jié)果又會(huì)怎樣呢？這個(gè)時(shí)候，神奇的事情發(fā)生了。這個(gè)罐子里面的球數(shù)將為0。對(duì)于任意一個(gè)球，設(shè)其編號(hào)為n，則在差(1/2)n-1分鐘到零點(diǎn)時(shí)該球?qū)⒈蝗〕?。也就是說(shuō)，對(duì)于任意球n，在零點(diǎn)時(shí)它都不在罐子里。因此，零點(diǎn)時(shí)罐子里球的個(gè)數(shù)為0。第

4、4頁(yè)/共47頁(yè)55意念與現(xiàn)實(shí)意念與現(xiàn)實(shí)(3): 一個(gè)例子一個(gè)例子對(duì)于有些人來(lái)說(shuō)，這個(gè)答案似乎不可接受。但又確實(shí)找不到駁斥的辦法。你能找出來(lái)嗎？也許這個(gè)答案是合理的，因?yàn)槟们蝽樞虻淖兓沟盟惴òl(fā)生了變化，即我們實(shí)際上討論的是兩個(gè)算法?？勺屑?xì)一想又覺(jué)得不對(duì)，因?yàn)閮蓚€(gè)算法都是每次放進(jìn) 10 個(gè)球，拿出1個(gè)球，即從根本上說(shuō)，這是兩個(gè)一樣的算法，怎么會(huì)有截然相反的結(jié)果呢?第5頁(yè)/共47頁(yè)66意念與現(xiàn)實(shí)意念與現(xiàn)實(shí)(4): 一個(gè)例子一個(gè)例子如果我們?cè)俅胃淖冊(cè)囼?yàn)中拿球的方式，將拿某個(gè)特定標(biāo)號(hào)的球改為取出任意標(biāo)號(hào)的球，即在差1分鐘到零點(diǎn)時(shí)，將標(biāo)號(hào)為110的10個(gè)球放進(jìn)罐子，然后從罐子里任意拿出一個(gè)球；在差1/2

5、分鐘到零點(diǎn)時(shí)，將標(biāo)號(hào)為1120的10個(gè)球放進(jìn)罐子，然后從罐子里任意拿出一個(gè)球；在差1/4分鐘到零點(diǎn)時(shí)，將標(biāo)號(hào)為2130的10個(gè)球放進(jìn)罐子，然后從罐子里任意拿出一個(gè)球這種拿球方式又將產(chǎn)生何種結(jié)果呢？答案是仍然是答案是仍然是0太不可思議了吧！這三個(gè)本質(zhì)相同的算法三個(gè)本質(zhì)相同的算法怎么有如此匪夷所思的結(jié)果呢？如果非要說(shuō)這三個(gè)算法有什么不同，就是拿球時(shí)的標(biāo)號(hào)不同。但難道標(biāo)號(hào)的不同使最后球的數(shù)量發(fā)生了變化?第6頁(yè)/共47頁(yè)77意念與現(xiàn)實(shí)意念與現(xiàn)實(shí)(5): 一個(gè)例子一個(gè)例子沒(méi)錯(cuò)，就是這個(gè)標(biāo)號(hào)對(duì)結(jié)果產(chǎn)生了深遠(yuǎn)影響。從某種意義上說(shuō)，標(biāo)號(hào)是虛的標(biāo)號(hào)是虛的，它只存在于我們的想象中，但確實(shí)對(duì)現(xiàn)實(shí)結(jié)果產(chǎn)生了影響，即我

6、們的思維使算法發(fā)生了變化我們的思維使算法發(fā)生了變化?；蛟S從另一個(gè)角度來(lái)看，這個(gè)問(wèn)題就是：沒(méi)有就是無(wú)窮，無(wú)窮就是沒(méi)有。它們之間也許根本沒(méi)有什么不同，它們的不同只存在于人們的想象或者意念想象或者意念中。也許這是為什么無(wú)窮的符號(hào) 是由兩個(gè)0連接而成的，從左右兩面看都是無(wú)有，而從中間看則是無(wú)窮。從這個(gè)意義上說(shuō)，算法是一種思維方式（Algorithmic Thinking），或者說(shuō)一種哲學(xué)。第7頁(yè)/共47頁(yè)8一個(gè)最簡(jiǎn)單的算法：1. 起床2. 吃早點(diǎn)3. 上早自習(xí)4. 上課5. 吃午飯6. 上課7. 吃晚飯8. 上晚自習(xí)9. 睡覺(jué)第8頁(yè)/共47頁(yè)9第9頁(yè)/共47頁(yè)1010第10頁(yè)/共47頁(yè)1111第11頁(yè)

7、/共47頁(yè)1212算法及其重要性質(zhì)算法及其重要性質(zhì) 算法：是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。 算法是由若干條指令組成的有窮序列，滿(mǎn)足性質(zhì)： (1)輸入：輸入：有0個(gè)或多個(gè)由外部提供的量作為算法的輸入。 (2)輸出：輸出：算法產(chǎn)生至少一個(gè)量作為輸出。（1個(gè)或多個(gè)） (3)確定性：確定性：組成算法的每條指令是清晰，無(wú)歧義的。 (4)有限性：有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。第12頁(yè)/共47頁(yè)1313算法與程序的區(qū)別算法與程序的區(qū)別 程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。 程序可以不滿(mǎn)足算法的性質(zhì)程序可以不滿(mǎn)足算法的性質(zhì)(4)

8、。 例如，操作系統(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é)果后便終止。第13頁(yè)/共47頁(yè)1414算法的描述方法算法的描述方法第14頁(yè)/共47頁(yè)1515第15頁(yè)/共47頁(yè)1616第16頁(yè)/共47頁(yè)1717第17頁(yè)/共47頁(yè)1818第18頁(yè)/共47頁(yè)1919第19頁(yè)/共47頁(yè)2020第20頁(yè)/共47頁(yè)2121第21頁(yè)/共47頁(yè)2222第22頁(yè)/共47頁(yè)2323第23頁(yè)/共47頁(yè)24241.2 算法復(fù)雜性分析算法復(fù)雜性分析第24頁(yè)/共47頁(yè)2525算法復(fù)雜性算法復(fù)雜性 算法復(fù)雜性

9、的高低體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源計(jì)算機(jī)資源的多少的多少上：所需資源越多，算法復(fù)雜性越高；反之，所需資源越少，算法復(fù)雜性越低。 算法的復(fù)雜性有：時(shí)間復(fù)雜性與空間復(fù)雜性 時(shí)間復(fù)雜性：時(shí)間復(fù)雜性：算法運(yùn)行所需要的時(shí)間資源量 空間復(fù)雜性：空間復(fù)雜性：算法運(yùn)行所需要的空間資源量 選用算法應(yīng)遵循的一個(gè)重要原則重要原則：當(dāng)給定的問(wèn)題有多種算法時(shí)，選擇其中復(fù)雜性最低者復(fù)雜性最低者 第25頁(yè)/共47頁(yè)2626算法復(fù)雜性算法復(fù)雜性(1) 時(shí)間/空間資源的量只依賴(lài)于算法要解的問(wèn)題的規(guī)模問(wèn)題的規(guī)模、算算法的輸入法的輸入和算法本身算法本身的函數(shù)。 分別用N、I和A表示算法要解問(wèn)題的規(guī)模、算法的輸入和算法本身，而

10、且用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)中） 第26頁(yè)/共47頁(yè)2727算法復(fù)雜性算法復(fù)雜性(2)設(shè)一臺(tái)計(jì)算機(jī)所提供的元運(yùn)算元運(yùn)算有k種種，分別記為O1, O2, , Ok同時(shí)，設(shè)每執(zhí)行一次執(zhí)行一次這些元運(yùn)算所需要時(shí)間分別為t1, t2, , tk對(duì)于給定的算法A，設(shè)用到元運(yùn)算Oi的次數(shù)為ei = ei (N, I), 那么kiiiINetINT1),(),(顯然，對(duì)于不同的N和I，T(N, I)有多種可能的值。對(duì)于給定問(wèn)題規(guī)模，算法A的時(shí)間復(fù)雜

11、性到底是多少？第27頁(yè)/共47頁(yè)2828最好、最壞與平均情況最好、最壞與平均情況最壞情況下的時(shí)間復(fù)雜性：),(maxmaxINT(N)TNDI),(max1INetkiiiDIN),(*1INetkiii),(*INT最好情況下的時(shí)間復(fù)雜性：),(minminINT(N)TNDI),(min1INetkiiiDIN),(1INetkiii),(INT平均情況下的時(shí)間復(fù)雜性：NDIINTIP(N)T),()(avgNDIkiiiINetIP),()(1其中D DN N是規(guī)模為N的合法輸入的集合合法輸入的集合；I*是DN中使T(N, I*)達(dá)到Tmax(N)的合法輸入.實(shí)踐表明：可操作性最好且最有

12、實(shí)際價(jià)值的時(shí)間復(fù)雜性 是DN中使T(N, )達(dá)到Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。II第28頁(yè)/共47頁(yè)2929第29頁(yè)/共47頁(yè)3030第30頁(yè)/共47頁(yè)3131第31頁(yè)/共47頁(yè)32算法漸近復(fù)雜性 設(shè)T(N)是算法A的復(fù)雜性函數(shù)，一般滿(mǎn)足：當(dāng) N+ ， T(N) +，即 對(duì)于T(N)，若存在t(N)，使得當(dāng)N+， T(N) - t(N) /T(N) 0 ，那么就說(shuō)t(N)是T(N)的漸近性態(tài)，或稱(chēng)為算法A的漸近復(fù)雜性。 在數(shù)學(xué)上， t(N)是T(N)的漸近表達(dá)式，是T(N)略去低階項(xiàng)留下的主項(xiàng)。例如， t(N)比T(N) 簡(jiǎn)單。2()log1T NNNN

13、2, ()t NNlim()NT N 第32頁(yè)/共47頁(yè)3333漸近符號(hào)漸近符號(hào)算法復(fù)雜性在漸近意義下的階：漸近意義下的記號(hào)：O、o 設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)正函數(shù)。 O的定義的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(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)的階的階。 例如： （1）由于對(duì)所有的N1有3N4N，則3N=O(N) （2）由于對(duì)所有的N1有N+10241025N，則N+1024=O(N) （3）由于對(duì)所有的N1有N2 N3 ，則N2=O(

14、N3) （4）由于對(duì)所有的N10有2N2+11N-103N2，則2N2+11N-10 =O(N2)第33頁(yè)/共47頁(yè)3434漸近符號(hào)漸近符號(hào) 根據(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)。 第34頁(yè)/共47頁(yè)3535漸近符號(hào)漸近符號(hào) 的定義的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(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 o的定義的定義：對(duì)于任意任意給定的0，都存在正整數(shù)N0，使得當(dāng)NN0時(shí)有f(N)/g(N),則稱(chēng)函數(shù)f(N)當(dāng)當(dāng)N充分大時(shí)