電子科技大學(xué)通信網(wǎng)理論基礎(chǔ)孫罡02-算法與分治.pptx

《電子科技大學(xué)通信網(wǎng)理論基礎(chǔ)孫罡02-算法與分治.pptx》由會(huì)員分享，可在線閱讀，更多相關(guān)《電子科技大學(xué)通信網(wǎng)理論基礎(chǔ)孫罡02-算法與分治.pptx（37頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

通信網(wǎng)絡(luò)理論基礎(chǔ),Part02:算法簡介／分治,2/39,Algorithm的由來,,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),3/39,,算法是什么？,,,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),設(shè)計(jì)范型,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),4／36,分治、貪心、動(dòng)態(tài)規(guī)劃、蠻力、隨機(jī)算法、回溯、分支定界，等等。,沒有哪種范型能適用于所有問題。,也可以看作是分析問題的思路。,從問題到求解思路的思考方向。,5/39,DivideandConquer（DC）,,,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),一種直觀的、最基礎(chǔ)的范型。,例子,6/39,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),7/39,,折半查找請(qǐng)查錯(cuò)，并修改Hint:以A={2,5,9}x=5為例來思考。,偽碼及實(shí)例,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),更好的例子：歸并排序,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),8／36,經(jīng)典：以至于幾乎每本算法教材都用它來引出分治。,為啥說“更好”？,有效：排序是一個(gè)重要的算法問題，歸并排序是最好的排序算法之一。,本課程將用它來引入復(fù)雜度分析的概念和基本原則。,對(duì)它的分析方法可以方便地?cái)U(kuò)展到“主定理”的證明。,遞歸：一個(gè)程序員永遠(yuǎn)的夢(mèng)魘。,MergeSort,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),9／36,遞歸返回后如何合并？,MergeStep（合并步驟）,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),10／36,運(yùn)行時(shí)間(RT)是多少？,運(yùn)行環(huán)境,CPU/OS/編譯器,指令的類別,只去數(shù)操作的次數(shù)。,問題實(shí)例？,問題實(shí)例規(guī)模的函數(shù)。,Mergestep的RT(T(m))？,初始化：2,每次循環(huán)：4,RT：MergeSort,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),11／36,Level0:最外層調(diào)用；問題的規(guī)模是n。,Level1:第一次調(diào)用遞歸,葉子：每個(gè)子問題都只含有1個(gè)元素的數(shù)組。,葉子在第幾層？,??????????,遞歸樹,第j層有幾個(gè)子問題？,????,第j層子問題的規(guī)模？,??/????,子問題的RT？,≤????/????,第j層所有子問題的總工作量？,≤??????(??/????)=????,Total？,≤????(??????????+??).QED,復(fù)雜度分析的原則,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),12／36,原則1:只關(guān)注“最壞情況”。,原則2:忽略常數(shù)和低階項(xiàng),任何規(guī)模為n的實(shí)例的操作時(shí)間的上界。,WHY?,WHY?,Moore定律=>在大規(guī)模實(shí)例下討論算法的運(yùn)行時(shí)間才有意義。,理解復(fù)雜度分析,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),13／36,不代表A的耗時(shí)總是少于B。,根據(jù)復(fù)雜度分析的結(jié)果說算法A比B好，是什么意思?,只能說隨著實(shí)例規(guī)模的增加，A的耗時(shí)增長更慢。,只能在“分類”的意義上評(píng)論好壞。,粗糙的分類評(píng)判，真的有意義嗎?,是的，還是有意義,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),14／36,能夠用多項(xiàng)式算法求解的問題=>“易解”,只能用指數(shù)或階乘算法求解的問題=>“不易解”,粗糙的定量評(píng)判也比經(jīng)驗(yàn)性的定性評(píng)判要好。,能夠揭示問題本質(zhì)上的難易程度。,只憑少量實(shí)例得到的判斷很難得到有價(jià)值的結(jié)論。,函數(shù)增長的漸近記號(hào),2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),15／36,令??=??,??,…,我們說????=??(????)是什么意思?,意味著n大到一定程度后，T(n)一定小于f(n)的常數(shù)倍。,BigO的證明（例1）,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),16／36,例1:????=????????+…+??????+????，證明:????=??????,證明要點(diǎn)：選擇合適的常數(shù)??和????，保證不等式成立。,待證：???≥??,????≤??????,????≤????????+…+??????+????≤????????+…+????????+????????=??????QED,BigO的證明（例2）,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),17／36,例2：證明:???≥??,????≠?????????,證明要點(diǎn)：反證法。,BigOmega和BigTheta,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),18／36,例子與練習(xí),2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),19／36,例3：????????+??=??(????)??(??)??(????),課后思考:????=????????+…+??????+????，證明:????=??????,課堂練習(xí):證明例3,MergeSort：Revisit,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),20／36,再來看這個(gè)結(jié)論，請(qǐng)問MergeSort的復(fù)雜度/RT是多少？,??(??????????),為什么不是??(????????????)？,以任何常數(shù)為底，對(duì)數(shù)函數(shù)都只差常數(shù)倍。,這在眾多的排序算法中，算是什么水平？,任何“基于比較”的排序算法中，最好的那一類即漸進(jìn)最優(yōu)算法。,基于比較的排序,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),21／36,任何基于兩兩比較的排序算法都可以表達(dá)為一棵決策樹。,給定問題實(shí)例{2,6,8}決策過程是什么？,給定{7,3,5}呢？,顯然，這是一棵完全二叉樹。,這是什么算法？,插入排序,決策樹模型的性質(zhì),2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),22／36,一次排序所需要的比較次數(shù)等于路徑長度。,上界為樹高h(yuǎn)。,任何正確的排序算法都應(yīng)該可以檢查到所有可能的排列。,所有排列都應(yīng)在葉子節(jié)點(diǎn)出現(xiàn)。,葉節(jié)點(diǎn)數(shù)目l：??≥??!,完全二叉樹中，l和h什么關(guān)系？,??≤????,故有：????≥??!,??≥????????!=??(??????????),QED,思考題／作業(yè),2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),23／36,我們沒有給出MergeSort的詳細(xì)偽碼。主要是沒有考慮邊界條件（例如n不是2的冪的情況）。請(qǐng)你自己根據(jù)你的經(jīng)驗(yàn)和理解來寫出一般情況下的算法偽碼。然后將你的偽碼與正確偽代碼對(duì)比。注意體會(huì)：與正確偽代碼相比，你少考慮了什么？下周堂上討論各自的體會(huì)。,這是一種很好的編程技能的訓(xùn)練和經(jīng)驗(yàn)的積累，務(wù)必先做后對(duì)比。希望以后自己也常做類似練習(xí)。,另一個(gè)分治的例子,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),24／36,都還記得小學(xué)老師教的吧？算法復(fù)雜度？,??(????),CANWEDOBETTER？,每個(gè)學(xué)算法的人都要讓自己成為偏執(zhí)狂。,如何分治？,??=??????????+????=??????????+??,a,b,c,d都是n/2位的整數(shù)。,例如：??=????,??=??????=????,??=????,兩個(gè)遞歸算法,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),25／36,??=??????????+????=??????????+??,分解方式也有了，合并公式也有了，設(shè)計(jì)個(gè)遞歸吧？,????=??????????+????????????+????+????,合并公式,Gauss’Trick:只用3個(gè)遞歸輸出同樣可以計(jì)算合并公式。,哪個(gè)更好？,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),26／36,兩個(gè)算法在遞歸調(diào)用之外做了哪些工作？,????=??????????+????????????+????+????,ALG#1：計(jì)算合并公式。=>??(??),ALG#2：計(jì)算合并公式；額外的加法。=>??(??),畫個(gè)遞歸樹來求解？,也行。但有個(gè)更好的辦法。,遞歸式,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),27／36,主方法：用來求解遞歸式的一種方法?！尽癇lackBox”】,遞歸式是什么？,基于分治的遞歸算法的RT，通?？梢员磉_(dá)出遞歸式。,ALG#1：????=????????+??(??),ALG#2：????=????????+??(??),????=????????+??(??)是什么算法？,MergeSort,主方法(MasterMethod),2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),28／36,對(duì)數(shù)的底到底要不要出現(xiàn)？,有時(shí)必須要；有時(shí)不必。,求解的例子(1/2),2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),29／36,例1：MergeSort,????=????????+??(??),復(fù)雜度？,??=??,??=??,??=??=>????????????,例2：????=????????+??(????),復(fù)雜度？,??=??,??=??,??=??=>??????,這個(gè)算法你覺得奇怪嗎？,求解的例子(2/2),2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),30／36,例3：ALG#1,????=????????+??(??),復(fù)雜度？,??=??,??=??,??=??=>??????,例4：ALG#2,????=????????+????,復(fù)雜度？,??=??,??=??,??=??=>??????????????,高斯還是真的牛人啊。,證明主定理,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),31／36,令????=??，并且????≤????????+???????！綛igO的定義】,假定n是b的冪?！疽话闱闆r的證明思路類似】,基本思路：擴(kuò)展MergeSort的分析方法——遞歸樹。,Level0:最外層調(diào)用；問題的規(guī)模是n。,Level1:a個(gè)子問題，n/b,葉子：子問題規(guī)模為1。Level??????????,第j層的子問題數(shù)目？,????,第j層的子問題規(guī)模？,??????,第j層總的RT？,≤??????????????=??????????????,總RT？,≤????????=????????????????????,對(duì)參數(shù)的理解,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),32／36,????≤????????+??????,??(??)≤????????=????????????????????,a是什么？,子問題數(shù)目的增長速率。,????是什么？,每個(gè)子問題RT的縮減速率。,??=????意味著什么？,??????意味著什么？,RT逐層增加。,葉節(jié)點(diǎn)的RT占主導(dǎo)。,關(guān)于求和的一個(gè)基本事實(shí),2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),33／36,令??≠??,??≥??,則有：??=????????=????+??????????,關(guān)鍵是：若??>??，則上式為??????。若??????時(shí)，??????????????????,而??????,????=??(????????????),有點(diǎn)兒沒對(duì)？????????????=?????????????,沒錯(cuò)。兩邊都取對(duì)數(shù)，以b為底。即可得證。,主定理證畢,你來試試？,2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),36／36,請(qǐng)用主定理來分析下面兩個(gè)算法的復(fù)雜度/RT.,課堂練習(xí)1:分治求數(shù)組的最大值?！居悬c(diǎn)侮辱智商】,課堂練習(xí)2:MergeSort-3。即每次分解為3個(gè)子問題?！静灰姷门丁?小結(jié),2017年春季通信網(wǎng)絡(luò)理論基礎(chǔ),37／36,,分治的概念,,,歸并排序,復(fù)雜度分析,,主方法,