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

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