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

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