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