《算法設(shè)計與分析》課件全套 林海 第1-9章 概述 - - 匹配與指派

算法設(shè)計與分析參考書算法導論（原書第3版）機械工業(yè)出版社算法設(shè)計技巧與分析，M.H.Alsuwaiyel著,電子工業(yè)出版社，吳偉昶等譯平時（代碼，作業(yè)，到課率）40%期末60%課程目標學習各種經(jīng)典算法設(shè)計算法解決問題分析算法性能算法實踐（課后）課程意義算法能力能夠準確辨別一個程序員的技術(shù)功底是否扎實算法能力是發(fā)掘程序員的學習能力與成長潛力的關(guān)鍵手段算法能力能夠協(xié)助判讀程序員在面對新問題時，分析并解決問題的能力算法能力是設(shè)計一個高性能系統(tǒng)、性能優(yōu)化的必備基礎(chǔ)算法是大廠考核的必然科目課程意義算法在計算機科學中的地位核心基礎(chǔ)課程1966年至2011年的圖靈獎獲得者中有19人直接或間接地與算法相關(guān)姚期智：Yao'smin-maxprinciple基本編程以數(shù)據(jù)結(jié)構(gòu)為中心的算法設(shè)計─基本算法設(shè)計方法通用算法設(shè)計─算法設(shè)計方法學識字寫小作文寫大文章與語文學習過程類比數(shù)據(jù)結(jié)構(gòu)程序設(shè)計語言算法設(shè)計與分析數(shù)據(jù)結(jié)構(gòu)1.基本概念算法是什么：算法(Algorithm)是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機制—百度百科。計算機解決問題的方法、步驟1.算法特征搜索給定一個數(shù)組，并給出一個數(shù)，要求在這個數(shù)組中尋找這個數(shù)，并返回相應的下標。二分搜索：對已經(jīng)排序好的數(shù)據(jù)進搜索1.算法特征二分搜索：對已經(jīng)排序好的數(shù)據(jù)進搜索1.算法特征二分搜索：偽代碼1.算法特征二分搜索：分析最好情況：中間數(shù)據(jù)，比較一次最差情況：1.算法特征排序：選擇排序找到n個元素中最小的一個元素，將其和第一個元素交換;在剩余的元素中找到最小的一個元素，將其和剩余元素的第一個元素交換;重復上面這個步驟，直到剩余元素為0。1.算法特征特征算法有輸入和輸出算法的每一步是可行的除了可行，每一步還必須是確定的算法必須在有限的時間(步驟)內(nèi)完成2.算法復雜度選擇排序為例2.算法復雜度選擇排序為例2.算法復雜度2.算法復雜度2.1時間復雜度：上界2.1時間復雜度：上界2.1時間復雜度：上界2.1時間復雜度：上界2.1時間復雜度：上界O運算具有如下運算規(guī)則2.1時間復雜度：下界2.1時間復雜度：下界2.1時間復雜度：下界2.1時間復雜度：同階2.1時間復雜度：同階2.1時間復雜度2.1時間復雜度2.1時間復雜度：例子2.1時間復雜度：例子2.1時間復雜度：例子2.1時間復雜度：例子2.1時間復雜度：例子2.1時間復雜度：例子2.2算法的時間復雜度計算執(zhí)行頻率最高的語句來作為算法的復雜度在迭代(循環(huán))的場景下，復雜度就是計算迭代次數(shù)最高的語句2.2算法的時間復雜度循環(huán)并列的情況：算法的復雜度是循環(huán)次數(shù)的相加2.2算法的時間復雜度循環(huán)嵌套的情況：算法的復雜度最里面嵌套2.3算法的空間復雜度為了求解問題的實例而執(zhí)行的計算步驟所需要的內(nèi)存空間數(shù)目例子選擇排序的空間復雜度為Θ(1)合并排序的空間復雜度為Θ(n)例子例子算法1：將所有的歌曲按照評分復制其編號，如歌曲1的評分為5.5，就將1復制55，歌曲10評分為6.6，則將10復制66。然后隨機的從這些編號中選取一個編號，選到的編號即為播放曲目。此算法的時間復雜度為O(1)，空間復雜度為n*E[歌曲的評分]。算法2：將所有的歌曲按照評分排列，并根據(jù)評分生成隨機區(qū)間，然后總區(qū)間的一個隨機值，這個值落在哪個區(qū)間，即播放相應的歌曲。如有4首歌其評分為[1,1.5,2,2]，則生成區(qū)間[0-1,1-2.5,2.5-4.5,4.5-6.5]4個區(qū)間，然后在[0-6.5]取一個隨機數(shù)，隨機數(shù)落在哪個區(qū)間，播放相應的歌曲。此算法的時間復雜度為O(logn)，空間復雜度為n*2。算法3：從1-n選取一個隨機數(shù)用于隨機選取一首歌曲。再從1-10選取一個隨機數(shù)，當選取歌曲的評分大于這個隨機數(shù)時，播放歌曲，否則不播放?？臻g復雜度為0，時間復雜度為隨機數(shù)的生成例子P331.4

1.6

1.11

1.13

1.16

1.23

1.261.31

1.35

3.數(shù)據(jù)結(jié)構(gòu)算法的實現(xiàn)離不開數(shù)據(jù)結(jié)構(gòu)。選擇一個合適的數(shù)據(jù)結(jié)構(gòu)對設(shè)計一個有效的算法有十分重要的影響。結(jié)構(gòu)化程序設(shè)計創(chuàng)始人NiklausWirth(瑞士蘇黎士高工)提出一個著名的論斷：“程序=算法+數(shù)據(jù)結(jié)構(gòu)”。1984年，Wirth因開發(fā)了Euler、Pascal等一系列嶄新的計算語言而榮獲圖靈獎,有“結(jié)構(gòu)化程序設(shè)計之父”之美譽我們已經(jīng)學過數(shù)組、隊列、棧、二叉樹等數(shù)據(jù)結(jié)構(gòu)，這里學習堆和不相交集3.1堆(Heap)在許多算法中，需要大量用到如下兩種操作：插入元素和尋找最大(小)值元素。為了提高這兩種運算的效率，必須使用恰當?shù)臄?shù)據(jù)結(jié)構(gòu)。普通隊列：易插入元素，但求最大(小)值元素需要搜索整個隊列。排序數(shù)組：易找到最大(小)值，但插入元素需要移動大量元素。堆則是一種有效實現(xiàn)上述兩種運算的簡單數(shù)據(jù)結(jié)構(gòu)。3.1堆(Heap)3.1堆(Heap)：特征堆是一棵完全二叉樹，堆所對應樹的節(jié)點的排列必須是從上到下，從左到右的依次排列，否則將不構(gòu)成堆在最大堆中，根節(jié)點值最大，葉子節(jié)點值較小，從根到葉子的一條路徑上，節(jié)點值以非升序排列任何一個父節(jié)點的值都大于等于其子節(jié)點的值，但節(jié)點的左右子節(jié)點值并無順序要求，且上層節(jié)點的值不一定大于下層節(jié)點的值堆中每個結(jié)點的子樹都是堆3.1堆(Heap)有n個節(jié)點的堆T,可以用一個數(shù)組a[1…n]來存儲，按照節(jié)點從上到下，從左到右的順序依次存儲用下面的方式來表示：T的根節(jié)點存儲在a[1]中假設(shè)T的節(jié)點x存儲在a[j]中，那么，它的左右子節(jié)點分別存放在a[2j]及a[2j+1]中(如果有的話)。a[j]的父節(jié)點如果不是根節(jié)點，則存儲在a[

j/2

]中3.1堆(Heap)3.1堆(Heap)：上移若某個節(jié)點a[i]鍵值大于其父節(jié)點的鍵值，就違背了堆的特性，需要進行調(diào)整。調(diào)整方法：上移。沿著a[i]到根節(jié)點的唯一一條路徑，將a[i]移動到合適的位置上：比較a[i]及其父節(jié)點a[

i/2

]的鍵值，若key(a[i])>key(a[

i/2

])，則二者進行交換，直到a[i]到達合適位置。3.1堆(Heap)：上移所需要的時間是O(logn).3.1堆(Heap)：下移假如某個內(nèi)部節(jié)點a[i](i≤

n/2

)，其鍵值小于兒子節(jié)點的鍵值,即key(a[i])<key(a[2i])或key(a[i]<key(a[2i+1])(如果右兒子存在)，違背了堆特性，需要進行調(diào)整。調(diào)整方法：下移。沿著從a[i]到子節(jié)點(可能不唯一，則取其鍵值較大者)的路徑，比較a[i]與子節(jié)點的鍵值，若key(a[i])<max(a[2i],a[2i+1])則交換之。這一過程直到葉子節(jié)點或滿足堆特性為止。3.1堆(Heap)：下移所需要的時間是O(logn).3.1堆(Heap)：插入思路：先將x添加到a[]的末尾，然后利用Sift-up，調(diào)整x在a[]中的位置，直到滿足堆特性。樹的高度為

logn,所以將一個元素插入大小為n的堆所需要的時間是O(logn).3.1堆(Heap)：刪除思路：先用a[n]取代a[i]，然后對a[i]作Sift-up或Sift-down)，直到滿足堆特性。所需要的時間是O(logn).3.1堆(Heap)：刪除堆頂元素輸入：堆H[1…n]輸出：返回最大鍵值元素，并將其從堆中刪除

x←H[1]2.delete(H,1)3.returnx3.1堆(Heap)：構(gòu)建方法1：從一個空堆開始，逐步插入A中的每個元素，直到A中所有元素都被轉(zhuǎn)移到堆中。時間復雜度為O(nlogn)因為插入一個元素需要logn，總共需要插入n個元素3.1堆(Heap)：構(gòu)建其他方法：直接對數(shù)據(jù)進行調(diào)整自上而下的調(diào)整一次調(diào)整需要O(nlogn)，總共需要log

n次調(diào)整，總復雜度為O(nlog2n)3.1堆(Heap)：構(gòu)建自下而上的調(diào)整調(diào)整一次即可（對以節(jié)點i為根的子樹進行調(diào)整）但復雜度依然是O(nlogn)優(yōu)化：1.葉子節(jié)點不需要調(diào)整；2.對子樹進行調(diào)整第i層的節(jié)點的調(diào)整最多交換?logn??i次3.1堆(Heap)：構(gòu)建例：給定數(shù)組A[1…10]={5,15,19,12,6,10,7,36,11,8，9,16}，構(gòu)建堆3.1堆(Heap)：構(gòu)建3.1堆(Heap)：構(gòu)建復雜度3.1堆(Heap)：構(gòu)建復雜度3.1堆(Heap)：d堆d堆：如三叉堆，四叉堆；樹的層數(shù)為logdn3.2不相交集在離散數(shù)學我們學過等價類是對集合S的一個劃分，對集合S的劃分形成了集合S的不相交集3.2不相交集不相交集可以用樹表示4個子集1:{1,7,10,11}，3:{2,3,5,6}，8:{4,8}，9:{9}并分別命名。11110726539843.2不相交集：查找、合并FIND(x):尋找包含元素x的集合的名字記root(x)為包含元素x的樹的根，則FIND(x)返回root(x).UNION(x,y):將包含元素x和y的兩個集合合并，重命名。執(zhí)行合并UNION(x,y)時，首先依據(jù)x找到root(x),記為u,依據(jù)y找到root(y)，記為v；然后，將u指向v。3.2不相交集：查找、合并3.2不相交集：秩和基于秩的合并按秩合并的順序決定了樹的高度。一個有n節(jié)點，且是通過不相交集合并操作形成的樹，其最大的高度是多少？3.2不相交集：秩和基于秩的合并3.2不相交集：秩和基于秩的合并3.2不相交集是不是通過基于秩的合并就總能得到最優(yōu)的不相交集?不一定：如有4個節(jié)點，先合并1和2，再合并3和4，不一定是最優(yōu)的如何優(yōu)化？合并時調(diào)整：復雜度從O(logn)變?yōu)镺(n)專門設(shè)置一個調(diào)整操作：也為O(n)部分解決方案：路徑壓縮3.2不相交集：路徑壓縮這個算法中為什么不對rank進行改變？345例：初始狀態(tài)：{1},{2},…,{9}612789執(zhí)行合并序列：UNION(1,2),UNION(3,4),UNION(5,6),UNION(7,8),得到的結(jié)果是：345612789繼續(xù)執(zhí)行合并序列：UNION(2,4),UNION(8,9),UNION(6,8),得到的結(jié)果是：345612789繼續(xù)執(zhí)行：FIND(5)得到的結(jié)果是：345612789繼續(xù)執(zhí)行UNION(4,8)繼續(xù)執(zhí)行：UNION(4,8)得到的結(jié)果是：345612789繼續(xù)執(zhí)行：FIND(1)得到的結(jié)果是：345612789算法設(shè)計與分析堆和不相交集數(shù)據(jù)結(jié)構(gòu)算法的實現(xiàn)離不開數(shù)據(jù)結(jié)構(gòu)。選擇一個合適的數(shù)據(jù)結(jié)構(gòu)對設(shè)計一個有效的算法有十分重要的影響。結(jié)構(gòu)化程序設(shè)計創(chuàng)始人NiklausWirth(瑞士蘇黎士高工)提出一個著名的論斷：“程序=算法+數(shù)據(jù)結(jié)構(gòu)”。1984年，Wirth因開發(fā)了Euler、Pascal等一系列嶄新的計算語言而榮獲圖靈獎,有“結(jié)構(gòu)化程序設(shè)計之父”之美譽我們已經(jīng)學過數(shù)組、隊列、棧、二叉樹等數(shù)據(jù)結(jié)構(gòu)，這里學習堆和不相交集堆(Heap)在許多算法中，需要大量用到如下兩種操作：插入元素和尋找最大(小)值元素。為了提高這兩種運算的效率，必須使用恰當?shù)臄?shù)據(jù)結(jié)構(gòu)。普通隊列：易插入元素，但求最大(小)值元素需要搜索整個隊列。排序數(shù)組：易找到最大(小)值，但插入元素需要移動大量元素。堆則是一種有效實現(xiàn)上述兩種運算的簡單數(shù)據(jù)結(jié)構(gòu)。堆(Heap)堆(Heap)：特征堆是一棵完全二叉樹，堆所對應樹的節(jié)點的排列必須是從上到下，從左到右的依次排列，否則將不構(gòu)成堆在最大堆中，根節(jié)點值最大，葉子節(jié)點值較小，從根到葉子的一條路徑上，節(jié)點值以非升序排列任何一個父節(jié)點的值都大于等于其子節(jié)點的值，但節(jié)點的左右子節(jié)點值并無順序要求，且上層節(jié)點的值不一定大于下層節(jié)點的值堆中每個結(jié)點的子樹都是堆堆(Heap)有n個節(jié)點的堆T,可以用一個數(shù)組a[1…n]來存儲，按照節(jié)點從上到下，從左到右的順序依次存儲用下面的方式來表示：T的根節(jié)點存儲在a[1]中假設(shè)T的節(jié)點x存儲在a[j]中，那么，它的左右子節(jié)點分別存放在a[2j]及a[2j+1]中(如果有的話)。a[j]的父節(jié)點如果不是根節(jié)點，則存儲在a[

j/2

]中堆(Heap)堆(Heap)：上移若某個節(jié)點a[i]鍵值大于其父節(jié)點的鍵值，就違背了堆的特性，需要進行調(diào)整。調(diào)整方法：上移。沿著a[i]到根節(jié)點的唯一一條路徑，將a[i]移動到合適的位置上：比較a[i]及其父節(jié)點a[

i/2

]的鍵值，若key(a[i])>key(a[

i/2

])，則二者進行交換，直到a[i]到達合適位置。堆(Heap)：上移所需要的時間是O(logn).堆(Heap)：下移假如某個內(nèi)部節(jié)點a[i](i≤

n/2

)，其鍵值小于兒子節(jié)點的鍵值,即key(a[i])<key(a[2i])或key(a[i]<key(a[2i+1])(如果右兒子存在)，違背了堆特性，需要進行調(diào)整。調(diào)整方法：下移。沿著從a[i]到子節(jié)點(可能不唯一，則取其鍵值較大者)的路徑，比較a[i]與子節(jié)點的鍵值，若key(a[i])<max(a[2i],a[2i+1])則交換之。這一過程直到葉子節(jié)點或滿足堆特性為止。堆(Heap)：下移所需要的時間是O(logn).堆(Heap)：插入思路：先將x添加到a[]的末尾，然后利用Sift-up，調(diào)整x在a[]中的位置，直到滿足堆特性。樹的高度為

logn,所以將一個元素插入大小為n的堆所需要的時間是O(logn).堆(Heap)：刪除思路：先用a[n]取代a[i]，然后對a[i]作Sift-up或Sift-down)，直到滿足堆特性。所需要的時間是O(logn).堆(Heap)：刪除堆頂元素輸入：堆H[1…n]輸出：返回最大鍵值元素，并將其從堆中刪除

x←H[1]2.delete(H,1)3.returnx堆(Heap)：構(gòu)建方法1：從一個空堆開始，逐步插入A中的每個元素，直到A中所有元素都被轉(zhuǎn)移到堆中。時間復雜度為O(nlogn)因為插入一個元素需要logn，總共需要插入n個元素堆(Heap)：構(gòu)建其他方法：直接對數(shù)據(jù)進行調(diào)整自上而下的調(diào)整一次調(diào)整需要O(nlogn)，總共需要log

n次調(diào)整，總復雜度為O(nlog2n)堆(Heap)：構(gòu)建自下而上的調(diào)整調(diào)整一次即可（對以節(jié)點i為根的子樹進行調(diào)整）但復雜度依然是O(nlogn)優(yōu)化：1.葉子節(jié)點不需要調(diào)整；2.對子樹進行調(diào)整第i層的節(jié)點的調(diào)整最多交換?logn??i次堆(Heap)：構(gòu)建例：給定數(shù)組A[1…10]={5,15,19,12,6,10,7,36,11,8，9,16}，構(gòu)建堆堆(Heap)：構(gòu)建堆(Heap)：構(gòu)建復雜度堆(Heap)：構(gòu)建復雜度堆(Heap)：d堆d堆：如三叉堆，四叉堆；樹的層數(shù)為logdn不相交集在離散數(shù)學我們學過等價類是對集合S的一個劃分，對集合S的劃分形成了集合S的不相交集不相交集不相交集可以用樹表示4個子集1:{1,7,10,11}，3:{2,3,5,6}，8:{4,8}，9:{9}并分別命名。1111072653984不相交集：查找、合并FIND(x):尋找包含元素x的集合的名字記root(x)為包含元素x的樹的根，則FIND(x)返回root(x).UNION(x,y):將包含元素x和y的兩個集合合并，重命名。執(zhí)行合并UNION(x,y)時，首先依據(jù)x找到root(x),記為u,依據(jù)y找到root(y)，記為v；然后，將u指向v。不相交集：查找、合并不相交集：秩和基于秩的合并按秩合并的順序決定了樹的高度。一個有n節(jié)點，且是通過不相交集合并操作形成的樹，其最大的高度是多少？不相交集：秩和基于秩的合并不相交集：秩和基于秩的合并不相交集是不是通過基于秩的合并就總能得到最優(yōu)的不相交集?不一定：如有4個節(jié)點，先合并1和2，再合并3和4，不一定是最優(yōu)的如何優(yōu)化？合并時調(diào)整：復雜度從O(logn)變?yōu)镺(n)專門設(shè)置一個調(diào)整操作：也為O(n)部分解決方案：路徑壓縮不相交集：路徑壓縮這個算法中為什么不對rank進行改變？345例：初始狀態(tài)：{1},{2},…,{9}612789執(zhí)行合并序列：UNION(1,2),UNION(3,4),UNION(5,6),UNION(7,8),得到的結(jié)果是：345612789繼續(xù)執(zhí)行合并序列：UNION(2,4),UNION(8,9),UNION(6,8),得到的結(jié)果是：345612789繼續(xù)執(zhí)行：FIND(5)得到的結(jié)果是：345612789繼續(xù)執(zhí)行UNION(4,8)繼續(xù)執(zhí)行：UNION(4,8)得到的結(jié)果是：345612789繼續(xù)執(zhí)行：FIND(1)得到的結(jié)果是：345612789算法設(shè)計與分析排序排序比較排序冒泡排序堆排序插入排序歸并排序線性排序桶排序計數(shù)排序基數(shù)排序1.1冒泡排序冒泡排序和選擇排序很相似，但冒泡排序是每次都選擇一個最大的元素，在第i次循環(huán)中，冒泡排序從未排序的元素中選擇一個最大的元素，并將其放在倒數(shù)第i個位置。比較：通過依次對兩兩相鄰的元素進行比較1.1冒泡排序一次冒泡過程1.1冒泡排序1.1冒泡排序和選擇排序比較1.2堆排序?qū)⒃亟M織成堆結(jié)構(gòu)，然后每次取堆頂元素1.2堆排序?qū)⒃亟M織成堆結(jié)構(gòu)，然后每次取堆頂元素1.2堆排序?qū)⒃亟M織成堆結(jié)構(gòu)，然后每次取堆頂元素1.2堆排序1.2堆排序是否穩(wěn)定排序？1.3插入排序每次都從剩余的元素中取第一個元素，將其插入到前面已經(jīng)排序好的序列中，使得插入后的序列依然是排序好的序列1.3插入排序1.3插入排序復雜度計算：插入排序是穩(wěn)定排序1.3插入排序平均復雜度：有沒有可能將插入排序的復雜度降低?1.3插入排序：希爾排序為了減少比較次數(shù)，可以跳著比，比如每隔4個元素比較一次1.3插入排序：希爾排序1.3插入排序：希爾排序1.3插入排序：希爾排序1.3插入排序：希爾排序1.3插入排序：希爾排序1.3插入排序：希爾排序1.4歸并排序（合并排序）二路歸并將兩個已經(jīng)排序好的數(shù)組(如數(shù)組A和數(shù)組B)進行合并，合并后的數(shù)組依然是排序好的1.4歸并排序二路歸并1.4歸并排序歸并排序1.4歸并排序多路歸并排序如4路歸并算法，和2路歸并比較1.4歸并排序多路歸并排序如4路歸并算法，和2路歸并比較1.4歸并排序多路歸并排序如4路歸并算法，和2路歸并比較1.4歸并排序多路歸并排序如4路歸并算法，和2路歸并比較1.4歸并排序多路歸并排序如4路歸并算法，和2路歸并比較有沒有可能降低比較次數(shù)?1.4歸并排序多路歸并排序如4路歸并算法，和2路歸并比較1.4歸并排序多路歸并排序1.4歸并排序多路歸并排序1.4歸并排序多路歸并排序1.4歸并排序基于錦標賽的多路合并在對k個排序好的子數(shù)組進行合并時，利用了一種聯(lián)賽的機制來選取最小值。1.4歸并排序勝者樹1.4歸并排序基于勝者樹的合并算法1.4歸并排序敗者樹1.4歸并排序基于敗者樹的合并算法1.4歸并排序基于敗者樹的合并算法2線性排序比較排序所能達到的最優(yōu)復雜度為O(nlog

n)能進一步降低排序的復雜度嗎？非比較排序只適合特定的場景2.1桶排序桶排序的基本步驟2.1桶排序幾個問題2.1桶排序幾個問題如果去比較一個元素是否屬于某個桶，則分發(fā)的復雜度為O(mn)。為了直接得出一個元素屬于哪個桶，需要計算元素所對應桶的下標。這個可以用前面任一復雜度為O(nlogn)的比較排序2.1桶排序算法2.1桶排序例子2.1桶排序2.2計數(shù)排序基本思想2.2計數(shù)排序問題2.2計數(shù)排序算法設(shè)置兩個數(shù)組B和C，其中B用于存放排序好的數(shù)組，而C起著計數(shù)的作用(也就是‘桶’的作用)。第一個for循環(huán)(語句4-6)對C進行初始化第二個for循環(huán)(語句7-9)統(tǒng)計每個元素的個數(shù)第三個for循環(huán)(語句10-12)就是依次對數(shù)組C中第1個元素開始到最后一個進行累加，其作用是統(tǒng)計某個元素前共有多少個元素。第四個for循環(huán)(語句13-16)從A數(shù)組的最后一個元素開始，通過C數(shù)組中對應的值確定其在B數(shù)組中的位置。2.2計數(shù)排序算法2.2計數(shù)排序2.3基數(shù)排序基本思想2.3基數(shù)排序流程2.3基數(shù)排序例子2.3基數(shù)排序問題：需要對‘位’上的數(shù)據(jù)進行排序，如何排序？桶排序或者計數(shù)排序算法2.3基數(shù)排序問題2.3基數(shù)排序例子2.3基數(shù)排序算法MSD是一個遞歸的過程基數(shù)排序也可以用于其他方面，如字母的排序算法設(shè)計與分析遞歸主要內(nèi)容基本概念遞歸的例子復雜度的遞歸求解1基本概念數(shù)學中的階乘可以用遞歸表示，也可以很好的解釋遞歸邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(jié)果1基本概念數(shù)學中的階乘可以用遞歸表示，也可以很好的解釋遞歸1基本概念執(zhí)行函數(shù)Factorial(3)時，會進入函數(shù)Factorial(2)，之后進入Factorial(1)，因Factorial(1)滿足邊界條件，返回結(jié)果1到函數(shù)Factorial(2)，F(xiàn)actorial(2)完整計算，并返回結(jié)果2到Factorial(3)，F(xiàn)actorial(3)得出結(jié)果6。進入遞歸函數(shù)時，調(diào)用函數(shù)依舊保留其狀態(tài)。也就是說如果執(zhí)行Factorial(n)，當遞歸調(diào)用到Factorial(1)時，系統(tǒng)中總共創(chuàng)建了100個Factorial函數(shù)1例子：斐波那契數(shù)列數(shù)列:0、1、1、2、3、5、8、13、21、34、......這個數(shù)列從第3項開始，每一項都等于前兩項之和1例子：漢諾塔問題1例子：漢諾塔問題1.1遞歸和迭代所有的遞歸實現(xiàn)都可以轉(zhuǎn)換為迭代實現(xiàn)嗎?反之，所有的迭代實現(xiàn)都可以通過遞歸實現(xiàn)嗎？迭代轉(zhuǎn)化為遞歸通常較簡單：二分搜索輸入：非降序排列的數(shù)組A[1…n]和元素x輸出：如果x=A[j],1

j

n,則輸出j,否則輸出0.1.low←1;high←n;j←02.while(low

high)and(j=0)3.mid←

(low+high)/2

4.ifx=A[mid]thenj←mid5.elseifx<A[mid]thenhigh←mid-16.elselow←mid+17.endwhile8.returnjbinarySearch(a,x,right,

left){while(left<=right){

middle=(left+right)/2;

if(x==a[middle])returnmiddle;

if(x>a[middle])return

binarySearch(a,

x,

right,

middle+1);

elsereturn

binarySearch(a,

x,

middle+1,

left);}

return-1;//未找到x}1.1遞歸和迭代迭代轉(zhuǎn)化為遞歸通常較簡單：選擇排序1.1遞歸和迭代迭代轉(zhuǎn)化為遞歸通常較簡單：插入排序1.1遞歸和迭代遞歸轉(zhuǎn)化為迭代時，要復雜很多如很難將漢諾塔問題轉(zhuǎn)化為循環(huán)迭代（需要通過棧）從實際上說，所有的迭代可以轉(zhuǎn)換為遞歸，但遞歸不一定可以轉(zhuǎn)換為迭代2.1生成排列遞歸實際上就是找n規(guī)模問題和<n規(guī)模問題(通常是n?1規(guī)模問題)的一個關(guān)系2.1生成排列如已知X={1,2,3}的全排列P(X)，Y={1,2,3,4}的全排列P(Y)和P(X)之間存在什么關(guān)系2.1生成排列2.1生成排列2.1生成排列算法的復雜度由if和else兩部分決定，直覺上覺得是else起決定作用輸出語句共執(zhí)行了nn！次，其中n！代表排序的總數(shù)，而每個排序有n個輸出所以復雜度由if決定為2.2整數(shù)劃分2.2整數(shù)劃分下面的方法是否可行？存在重復計算2.2整數(shù)劃分2.2整數(shù)劃分2.2整數(shù)劃分3時間復雜度計算迭代次數(shù)頻度分析使用遞歸方程3.1計算迭代次數(shù)

計算迭代次數(shù)通常，程序的運行時間和程序的迭代次數(shù)成比例。因此計算程序的迭代次數(shù)就可以作為算法運行時間的指示器。這在很多算法中都可以得到應用，如查找、排序等等3.1計算迭代次數(shù)

輸入：n(n=2k

，k為某一正整數(shù))輸出：count（迭代次數(shù)）1.count←02.whilen≥13.forj←1ton4.count←count+1//執(zhí)行一次耗費時間設(shè)為a5.endfor6.n←n/2//執(zhí)行一次耗費時間設(shè)為d7.endwhile8.returncount分析：while迭代的次數(shù)是k+1次(因為n≥1可以寫成n≥20,運行過程n=2k→20)，k=logn。在每次while循環(huán)里面for依次執(zhí)行n，n/2,n/4,…,1次，所以，算法的時間復雜度為：3.1計算迭代次數(shù)

為什么在上面計算算法的時間復雜度時不考慮step6,而只是考慮step4呢？如果同時考慮step4和step6，我們有小結(jié)：使用計算迭代次數(shù)的技術(shù)來分析算法的時間復雜度時，只需要考慮最深層次的迭代。3.2頻度分析

頻度分析對于有些算法，計算迭代次數(shù)非常麻煩，有時甚至是不可能的。這時候，可以使用頻度分析。在MEGE算法中，賦值運算具有最大頻度將A的每個元素移到B又將B的每個元素移到A所以算法復雜度為2n3.2最壞情況和平均情況分析平均情況分析：通?？紤]均勻分布情況下的復雜度如插入排序中，將第i個元素插入到前面已經(jīng)排序好的數(shù)組中插入到第1個位置，比較i-1次插入到其他位置（位置j），比較i-j+1次平均比較次數(shù)為：3.2最壞情況和平均情況分析插入排序總的平均比較次數(shù)為：插入排序最差的比較次數(shù)為：3.3復雜度的遞歸求解3.3復雜度的遞歸求解3.3.1展開法3.3.1展開法3.3.2代入法步驟先猜測解的形式再通過數(shù)學歸納法證明適用于對遞歸形式比較熟悉的情況代入法另外一用法是對展開法或者遞歸樹法求得的復雜度，進行進一步的確認3.3.2代入法這個復雜度的遞歸式和快速排序的復雜度遞歸式類似，猜測其也為O(nlogn)3.3.2代入法邊界條件：3.3.2代入法3.3.2代入法3.3.2代入法3.3.2代入法3.3.2代入法3.3.3遞歸樹方法3.3.3遞歸樹方法首先將T(n)看出一個節(jié)點，如圖展開將每個子節(jié)點按照T(n)方式展開從圖中可知，遞歸樹總共有l(wèi)ogn層，對每層所有節(jié)點的復雜度進行累加，得出每層的復雜度為cn，葉子層的復雜度為nT(1)=nc′。所以總的復雜度T(n)=nlogn3.3.3遞歸樹方法首先將復雜度的遞歸式展開為樹的形式之后，計算樹每層的復雜度最后，將所有層的復雜度相加，得到T(n)的復雜度3.3.3遞歸樹方法這棵樹并不是滿二叉樹，最短路徑為n/2，最長路徑為n。3.3.3遞歸樹方法3.3.3遞歸樹方法3.3.4主方法主要應用于先從簡單的形式3.3.4主方法3.3.4主方法3.3.4主方法3.3.4主方法3.3.4主方法3.3.5幾種遞歸形式的分析3.3.5幾種遞歸形式的分析3.3.5幾種遞歸形式的分析3.3.5幾種遞歸形式的分析此公式的求和項中，貌似每一項都是Θ(n2)，所以很容易錯誤的認為期望值也是Θ(n2)3.3.5幾種遞歸形式的分析3.3.5幾種遞歸形式的分析3.3.5幾種遞歸形式的分析算法設(shè)計與分析分治主要內(nèi)容分治的基本方法快速排序最大子數(shù)組問題最近點對問題尋找第k小元素棋盤覆蓋分治的思想規(guī)模比較大的問題分解成較小的問題，較小的問題再解決成更小的問題，直到容易解決為止對較小問題的解決，是繼續(xù)分解--遞歸方程直到容易解決為止（通常為1個元素）--邊界條件1合并排序（分治）52分解47分解13分解26分解5247分解1326分解52471326分解524713261合并排序（分治）25合并47合并13合并26合并2457合并1236合并12234567合并524713261合并排序（分治）首先對原數(shù)組分解成左右兩個子數(shù)組（減小問題的規(guī)模）（語句4-5）對這兩個子數(shù)組進行排序，怎么排序？遞歸的調(diào)用原函數(shù)進行排序即可（語句6-7）最后通過合并操作對排序后的子數(shù)組進行合并（語句8）1分治步驟分解：將原問題分解成規(guī)模較小的子問題原問題P可以被分成多個子問題P1,P2,···,Pk子問題的形式需要和原問題一致解決：通過遞歸的方式解決子問題P1,P2的獨立解，以及P1,P2共同相關(guān)的解合并：對子問題的解進行合并，形成原問題的解。1分治步驟原問題(sizen)子問題1子問題2子問題k…子問題21子問題22子問題2k…:分解:遞歸解決

:合并2快速排序快速排序的基本步驟2快速排序：分解主元的選擇：第一個元素或者最后一個元素問題：相同元素的位置發(fā)生了改變2快速排序：分解主讓i指向小于等于主元素部分的最后一個元素，j指向大于主元素部分的最后一個元素2快速排序2快速排序：復雜度分析對半分按比例分2快速排序：復雜度分析常數(shù)劃分算法期望復雜度3最大子數(shù)組問題3最大子數(shù)組問題最大子數(shù)組的基本步驟3最大子數(shù)組問題最大子數(shù)組的基本步驟3最大子數(shù)組問題橫跨在兩個子問題上的最大子數(shù)組只要依次遍歷左右數(shù)組的所有子數(shù)組，即可找到橫跨在兩個子問題上的最大子數(shù)組復雜度3最大子數(shù)組問題復雜度4最近點對問題窮舉求解將每一個點都與其它n-1個點的距離算出來，然后找出其中最小的即可4最近點對問題最近點對的基本步驟4最近點對問題最近點對的基本步驟4最近點對問題為此，我們設(shè)δ=min{δl,δr}，并在直線L左右兩邊分別畫出寬度為δ的區(qū)域，如圖中的Sl′和Sr′，顯而易見，小于min{δl,δr}的點對只可能出現(xiàn)在這個兩個區(qū)域。那么，是不是只要比較所有Sl′和Sr′間點對的距離即可4最近點對問題只需要比較圖中所示的δ?2δ長方形上的點即可，落在這個長方形外的點和p的距離一定是大于δ的。這個長方形區(qū)域最多只能放6個點

哪6個點？在y軸上投影，相鄰的8個點

4最近點對問題復雜度還能不能進一步降低？4最近點對問題復雜度4最近點對問題5尋找第k小元素5尋找第k小元素5尋找第k小元素如何將原數(shù)組分成兩個子問題？尋找一個中間元素如何找到這個處于中間位置的元素m？將n個元素劃分成m個組(通常是每組5個元素)，取每組的中間元素，再取這些中間元素的中間元素怎么找到中間元素的中間元素？遞歸調(diào)用5尋找第k小元素哪個子問題需要被舍棄？元素分成3組，小于m，等于m，和大于m，找到相應的組，舍棄其他組一

為方便演示，設(shè)閾值為6?，F(xiàn)要尋找下面數(shù)組A中的第13小元素：A={8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7}{8,33,17,51,57}{49,35,11,25,37}{14,3,2,13,52}{12,6,29,32,54}{5,16,22,23,7}{8,17,33,51,57}{11,25,35,37,49}{2,3,13,14,52}{6,12,29,32,54}{5,7,16,22,23}M={33,35,13,29,16}mm=29A1={8,17,11,25,14,3,2,13,12,6,5,16,22,23,7}A2={29}A3={33,51,57,49,35,37,52,32,54}因為k=13<|A1|=15{8,17,11,25,14}{3,2,13,12,6}{5,16,22,23,7}M={14,6,16}mm=14{8,11,14,17,25}{2,3,6,12,13}{5,7,16,22,23}A={8,17,11,25,14,3,2,13,12,6,5,16,22,23,7}A1={8,11,3,2,13,12,6,5,7}A2={14}A3={17,25,16,22,23}M={14,6,16}mm=14因為k=13>|A1|+|A2|＝9＋1=10因為|A3|<p=6閾值{16,17,22,23,25,}returnA[3]因為(3=13-9-1)5尋找第k小元素5尋找第k小元素：復雜度5尋找第k小元素：復雜度5尋找第k小元素：復雜度5尋找第k小元素：以平均值為中項元素對S中所有的元素求一個均值，用這個均值對數(shù)組進行劃分即可5尋找第k小元素：5尋找第k小元素：6棋盤覆蓋問題：6棋盤覆蓋問題：6棋盤覆蓋問題：復雜度遞歸式（n為棋盤格子總數(shù)）：算法設(shè)計與分析動態(tài)規(guī)劃主要內(nèi)容動態(tài)規(guī)劃的基本性質(zhì)和步驟最大子數(shù)組問題0-1背包問題旅行商問題最長公共子序列狀態(tài)壓縮動態(tài)規(guī)劃1引例：斐波那契數(shù)遞歸形式的算法：procedurefib(n)ifn=1orn=2thenreturn1elsereturnfib(n-1)+fib(n-2)1引例：斐波那契數(shù)存在大量重復計算當n=100時，用遞歸求解的時間T(100)≈3.53×1020,若每秒計算108次，需111,935年1解決方法從第1個元素開始計算，從而消除重復計算f1←1f2←1fori←3tonresult←f1+f2f1←f2f2←resultendforreturnresult1基本性質(zhì)和分治類似動態(tài)規(guī)劃也是將原問題分解為子問題求解和分治不同不是通過遞歸的方式，而是自低向上的求解問題1基本性質(zhì)動態(tài)規(guī)劃和分治的比較需要列出遞歸式1機器人行走1機器人行走分治1機器人行走分治需要計算多少次？55次

1機器人行走動態(tài)規(guī)劃自底向上的計算：12次1基本性質(zhì)動態(tài)規(guī)劃適用的場景子問題并不獨立，即子問題是可能重復的主要用于優(yōu)化問題（求最優(yōu)解），且問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)1最優(yōu)子結(jié)構(gòu)性質(zhì)最短路徑問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（替換法證明）1最優(yōu)子結(jié)構(gòu)性質(zhì)最長路徑問題不具有最優(yōu)子結(jié)構(gòu)性質(zhì)1基本步驟定義子問題，并分析最優(yōu)解的結(jié)構(gòu)特征分治通常是將原問題對半分，而動態(tài)規(guī)劃是將n規(guī)模的問題分解成n?1規(guī)模的問題找出最優(yōu)解對應的最優(yōu)值，并遞歸地定義最優(yōu)值以自底向上的方式計算出最優(yōu)值根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解2最大子數(shù)組問題子問題的定義：基于分治的方法2最大子數(shù)組問題遞歸定義最優(yōu)值是否存在重復計算？2最大子數(shù)組問題動態(tài)規(guī)劃：n-1為原問題n的子問題求解改為：包含數(shù)組最后一個元素的最大子數(shù)組2最大子數(shù)組問題動態(tài)規(guī)劃：最大子數(shù)組問題最優(yōu)解的結(jié)構(gòu)特征找出最優(yōu)解對應的最優(yōu)值，并遞歸地定義最優(yōu)值2最大子數(shù)組問題動態(tài)規(guī)劃：自底向上的求解最優(yōu)值2最大子數(shù)組問題動態(tài)規(guī)劃：根據(jù)b值矩陣得出最優(yōu)解3

0-1背包問題3

0-1背包問題分析0-1背包問題最優(yōu)解的結(jié)構(gòu)特征一種情況是第n個物品不包括在最優(yōu)解里第二種情況是第n個物品包括在最優(yōu)解里3

0-1背包問題找出0-1背包問題最優(yōu)解對應的最優(yōu)值，并遞歸地定義最優(yōu)值3

0-1背包問題自底向上的求解最優(yōu)值3

0-1背包問題自底向上的求解最優(yōu)值3

0-1背包問題根據(jù)m值矩陣得出最優(yōu)解算法復雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計算時間。當背包容量c很大時，算法需要的計算時間較多。例如，當c>2n時，算法需要Ω(n2n)計算時間。4旅行商問題4旅行商問題旅行商問題最優(yōu)解的結(jié)構(gòu)特征最優(yōu)子結(jié)構(gòu)性質(zhì)旅行商問題的子問題是顯然重疊的假設(shè)路徑c1...cn?1cn

是城市{c1,c2,...,cn?1,cn}的最短路徑，取這個路徑子路徑c1...cn-1

必然是城市{c1,c2,...,cn-1}中從c1

到cn-1

經(jīng)過其他城市一次且僅一次的最短路徑。如下兩個路徑c1c2c3c4...cn

和c1c3c2c4...cn

都具有相同的子路徑c4...cn?1cn。4旅行商問題旅行商問題最優(yōu)解對應的最優(yōu)值，并遞歸地定義最優(yōu)值4旅行商問題旅行商問題最優(yōu)解對應的最優(yōu)值，并遞歸地定義最優(yōu)值4旅行商問題自底向上求解最優(yōu)值4旅行商問題4旅行商問題4旅行商問題自底向上求解最優(yōu)值在此算法中，因TSP(c1,C,ci)中的c1

可忽略，我們用一個二維數(shù)組TP[C][ci]存儲TSP(c1,C,ci)的值4旅行商問題構(gòu)造最優(yōu)解While循環(huán)(語句4-18)依次往最短路徑添加城市，每次添加實際上就是找出下一層哪一個TSP和當前城市c?形成了最短回路5最長公共子序列若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個嚴格遞增下標序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應的遞增下標序列為{2，3，5，7}。給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。

窮舉法(Brute-Force)：找出X字符串所有可能的子序列(2n)；對于X的每一個子序列，判斷其是否是Y的一個子序列,需要的時間為Θ(m);求max;總的時間為Θ(m2n).5最長公共子序列5最長公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk}，則5子問題的遞歸結(jié)構(gòu)3115自底向上計算c[i][j]

兩個序列分別為X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>j0123456iyiBDCABA0xi1A2B3C4B5D6A7B000000000000004432214332213322213322112222112211111110003125計算最優(yōu)值由于在所考慮的子問題空間中，總共有θ(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。3135構(gòu)造最長子序列6狀態(tài)壓縮動態(tài)規(guī)劃集合狀態(tài)壓縮用二進制表示集合，之后用整型表示二進制，如旅行商問題中的TP數(shù)組空間狀態(tài)壓縮自底向上的方法求解最優(yōu)值的過程中，壓縮最優(yōu)值的存儲空間6集合狀態(tài)壓縮整數(shù)的一些基本的位操作6集合狀態(tài)壓縮旅行商問題的狀態(tài)壓縮TP[C][ci]數(shù)組通過狀態(tài)壓縮可以用二維數(shù)組TP[m][n?1]表示，其中m=2n?1

?1那么如何依次計算這個TP表?按行依次計算6集合狀態(tài)壓縮旅行商問題的狀態(tài)壓縮TP[C][ci]數(shù)組通過狀態(tài)壓縮可以用二維數(shù)組TP[m][n?1]表示，其中m=2n?1

?1那么如何依次計算這個TP表?按行依次計算6集合狀態(tài)壓縮旅行商問題的狀態(tài)壓縮需要判斷一下:

j所代表的城市集合C是否包含了i所代表的城市，如果不包含，就無需做任何處理，如包含，則依次比較j集合所有下一層的TP值6空間狀態(tài)壓縮采用一種維度更低的數(shù)據(jù)結(jié)構(gòu)來存儲高維度的數(shù)據(jù)結(jié)構(gòu)如在機器人行走的例子中，可以采用一維數(shù)組來存儲path值從而降低空間復雜度設(shè)機器人行走按行依次計算，所以按行進行壓縮6空間狀態(tài)壓縮6空間狀態(tài)壓縮同時需要第j?1列的i?1行和i行的狀態(tài)值，所以，此時我們必須使用額外的變量來臨時存儲(i?1,j?1)的狀態(tài)值6空間狀態(tài)壓縮按列壓縮算法設(shè)計與分析貪心算法主要內(nèi)容基本概念小數(shù)背包和0-1背包最小生成樹霍夫曼編碼1基本概念是指算法每次做選擇的時是‘貪心’的，也就是盡量選擇從目前看來是最好的如旅行商問中，設(shè)目前處于城市ci，那么就選擇一條從ci到其他城市(還沒有的城市)最短的邊局部最優(yōu)選擇，并不一定能達到全局最優(yōu)對某些問題是可以得到全局最優(yōu)解，但對另外一些問題是無法獲得全局最優(yōu)解的1例子：錢幣兌換1錢幣兌換：動態(tài)規(guī)劃步驟11錢幣兌換：動態(tài)規(guī)劃步驟21錢幣兌換：動態(tài)規(guī)劃步驟31錢幣兌換：動態(tài)規(guī)劃步驟41錢幣兌換貪心算法先兌換大面額的硬幣，只有在大面額的硬幣無法兌換時，才兌換小面額的硬幣1錢幣兌換貪心算法和動態(tài)規(guī)劃1貪心解是最優(yōu)解嗎？需要證明：貪心算法每次選出的解都屬于最優(yōu)解集合替換法歸納法1貪心解是最優(yōu)解嗎？替換法用貪心算法得出的解(x1,x2,···,xn)和最優(yōu)解(y1,y2,···,yn)中的元素依次進行比較，如果元素xi

和yi

相同，則將最優(yōu)解中的yi替換成xi，顯然替換后的解還是最優(yōu)解;如果不同，還是要將yi

替換成xi，但這時，還需要證明替換后的解依然是最優(yōu)解1貪心解是最優(yōu)解嗎？歸納法貪心選擇是正確的

問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)2小數(shù)背包2小數(shù)背包2小數(shù)背包2小數(shù)背包小數(shù)背包貪心算法的正確性證明：替換法設(shè)物品都已經(jīng)按照性價比排好，并設(shè)X=(x1,x2,···,xk,xk+1,···,xn)是貪心算法得出的解，其中0≤xi≤1設(shè)最優(yōu)解為Y=(y1,y2,···,yn)，其中0≤yi≤1找到第一個不相同的元素j，xj

≠yj

2小數(shù)背包2小數(shù)背包2

0-1背包貪心算法不一定能夠得出0-1背包的最優(yōu)解3最小生成樹3最小生成樹3最小生成樹：Kruskal算法3最小生成樹：Kruskal算法3

Kruskal算法對邊排序(語句7)復雜度為O(mlogm)，第二個for循環(huán)(語句8-13)執(zhí)行m次，循環(huán)體內(nèi)的FIND語句(語句9)的復雜度為O(logn)，即第二個for循環(huán)的復雜度為O(mlogn)，所以算法總復雜度為O(mlogm+mlogn)=O(mlogm)3

最小生成樹3

最小生成樹3

最小生成樹3

最小生成樹：Prim算法3

最小生成樹：Prim算法3

最小生成樹：Prim算法4霍夫曼編碼數(shù)據(jù)壓縮應用網(wǎng)絡(luò)、磁盤數(shù)據(jù)壓縮減少數(shù)據(jù)傳輸量減少數(shù)據(jù)存儲量.霍夫曼編碼廣泛的應用在數(shù)據(jù)壓縮，可節(jié)省約20%-90%的數(shù)據(jù)量4霍夫曼編碼4霍夫曼編碼4霍夫曼編碼定長和變長編碼形成的編碼樹最優(yōu)編碼樹，每個非葉子節(jié)點都有兩個子節(jié)點4霍夫曼編碼最優(yōu)編碼樹的每個節(jié)點都有兩個節(jié)點4霍夫曼編碼前綴碼：沒有任何碼字是其他碼字的前綴編碼：將每個碼字連接起來即可解碼需要從一串編碼中解碼出每個碼字。簡單，因為沒有重復的前綴01101000，很容易解碼出為單詞‘bad’霍夫曼編碼是前綴碼4霍夫曼編碼：算法流程4霍夫曼編碼：算法流程因步驟3要重復n?1次，每次都需排序，復雜度為O(n2

logn)如果將A中的元素按照頻率組織成最小堆，則取兩個頻率最低元素的復雜度為logn，插入一個合并后元素的復雜度也是logn，所以總體復雜度降到了O(nlogn)4霍夫曼編碼：例子4霍夫曼編碼：例子4霍夫曼編碼4霍夫曼編碼4霍夫曼編碼算法設(shè)計與分析圖算法主要內(nèi)容深度優(yōu)先搜索廣度優(yōu)先搜索單源最短路徑多源最短路徑1基本概念1基本概念：圖的遍歷圖的遍歷是求解圖問題的基礎(chǔ)。和樹的遍歷類似，圖的遍歷希望從圖中某一頂點出發(fā)，對其余各個頂點都訪問一次，但比樹的遍歷要復雜得多。圖的任一頂點都有可能和其余頂點相鄰接，因此在訪問了某頂點后，可能沿著某條路徑搜索以后，又回到該頂點。通常有兩種遍歷圖的方法：深度優(yōu)先搜索、廣度優(yōu)先搜索。他們都適合于無向圖和有向圖。1深度優(yōu)先搜索1深度優(yōu)先搜索流程1深度優(yōu)先搜索流程32014v=2的DFS序列：21034遍歷過程結(jié)束32014DFS思路：距離初始頂點越遠越優(yōu)先訪問！1深度優(yōu)先搜索通過對圖G進行深度優(yōu)先搜索，按照節(jié)點的遍歷順序會生成一棵樹，稱為深度優(yōu)先搜索生成樹，當原圖為非聯(lián)通時，會生成深度優(yōu)先搜索生成森林每個節(jié)點標注兩個屬性，一個稱為先序號(用predfn表示)，另一個屬性稱為后序號(用postdfn表示)。1深度優(yōu)先搜索dfs(v)函數(shù)共被調(diào)用了n次，而每次調(diào)用dfs(v)函數(shù)都需要對節(jié)點v所連的邊都遍歷一次(dfs(v)函數(shù)中的for循環(huán))，所以for循環(huán)總共執(zhí)行了2m次，復雜度為Θ(2m)，所以總的復雜度為Θ(2m+n)1.1無向圖深度優(yōu)先搜索無向圖的邊根據(jù)深度優(yōu)先搜索可分成兩類1.1無向圖深度優(yōu)先搜索：例子1.1無向圖深度優(yōu)先搜索：例子1.1無向圖深度優(yōu)先搜索通過堆棧實現(xiàn)1.2有向圖深度優(yōu)先搜索有向圖的邊根據(jù)深度優(yōu)先搜索可分成兩類1.2有向圖深度優(yōu)先搜索：例子1.2有向圖深度優(yōu)先搜索：例子為何DFS用于無向圖時，不存在前向邊及橫跨邊?(1)前向邊（v，w）(2)橫跨邊（w,v）1.3深度優(yōu)先搜索：應用尋找圖的關(guān)節(jié)點顯然，如果G是連通的，那么在移除關(guān)節(jié)點和與其關(guān)聯(lián)的邊后，圖變?yōu)椴贿B通的1.3尋找圖的關(guān)節(jié)點用α(v)表示某一節(jié)點v自身的層級，用β(v)表示節(jié)點能夠到達的層級節(jié)點的α值可以直接用深度優(yōu)先搜索的先序號表示β值則由以下幾種情況決定:

1.3尋找圖的關(guān)節(jié)點根節(jié)點只要判斷其子節(jié)點的個數(shù)是否大于等于2即可非根節(jié)點：當要判斷某一個節(jié)點v是不是關(guān)節(jié)點，需要比較節(jié)點v的α值和其子節(jié)點的β值，只要任一子節(jié)點的β大于等于節(jié)點v的α值(說明這個子節(jié)點沒法到達比節(jié)點v更上層級)，則節(jié)點v為關(guān)節(jié)點，否則為非關(guān)節(jié)點1.3尋找圖的關(guān)節(jié)點Predfn用于計算\alpah值和\beta值rtdegree是深度優(yōu)先搜索樹根的度1.3尋找圖的關(guān)節(jié)點初始化節(jié)點v的alpha和beta為predfn依次訪問節(jié)點v的邊如果邊的另一個節(jié)點沒有訪問（樹邊），遞歸訪問，遞歸回來后，更新beta值，并判斷是否關(guān)節(jié)點如果邊的另一個節(jié)點已經(jīng)訪問（回邊），更新beta值1.3尋找圖的關(guān)節(jié)點a(1,1)，b(2,2)，c(3,3)，

d(4,4)，e(5,5)，

f(6,6)訪問efb,min{f.beta,b.alpha}=f(6,2)min{e.beta,f.beta}=e(5,2),d(4,2)，c(3,2),b(2,2)(b為關(guān)節(jié)點)g(7,7),h(8,8),i(9,9),j(10,10),k(11,11)k(11,9),j(10,9),i(9,9)(關(guān)節(jié)點),h(8,1)(關(guān)節(jié)點),h(7,1),a(1,1)decbaghijkf1.3圖的回路判斷問題：若G=(V,E)為一個有n個頂點和m條邊的有向或是無向圖。要測試G中是否包含有一個回路。方法：對G施加深度優(yōu)先搜索，如果探測到一個回邊，那么可以判定G中含有回路；否則G中無回路。注意：如果G是連通的無向圖，則不需要對G進行深度優(yōu)先搜索來判定是否有回路。G無回路，當且僅當|E|=|V|-1。1.3拓撲排序給定一個有向無回路圖(DirectedAcyclicGraph,DAG)G=(V,E)。拓撲排序是為了找到圖頂點的一個線性序，使得：如果(v,w)∈E,那么，在線性序中，v在w之前出現(xiàn)。我們假設(shè)在DAG中只有唯一一個入度為0的頂點；如果有一個以上的頂點入度為0，可以通過添加一個新的頂點s，然后將s指向所有入度為0的頂點，這樣s就成為唯一一個入度為0的頂點。decbafgabdcefg1.3拓撲排序拓撲排序的實現(xiàn)：從入度為0的頂點開始，對DAG實施深度優(yōu)先搜索。遍歷完成后，計數(shù)器postdfn恰好對應于一個在DAG中頂點的反拓撲序得到拓撲序：在DFS算法中恰當位置增加輸出語句，然后將輸出結(jié)果反轉(zhuǎn)。在DFS算法中恰當位置增加頂點入棧操作，然后依次取棧頂元素輸出。1.3拓撲排序decbafgdecbafgssdcbafge86735214abcedfg1.3

網(wǎng)絡(luò)頁面檢索深度優(yōu)先搜索是一種在開發(fā)爬蟲早期使用較多的方法優(yōu)點是能遍歷一個Web站點或深層嵌套的文檔集合；缺點是因為Web結(jié)構(gòu)相當深,，有可能造成一旦進去，再也出不來的情況發(fā)生。主要內(nèi)容深度優(yōu)先搜索廣度優(yōu)先搜索單源最短路徑多源最短路徑2廣度優(yōu)先搜索2廣度優(yōu)先搜索v=2的BFS序列：21340遍歷過程結(jié)束3201432014BFS思路：距離初始頂點越近越優(yōu)先訪問！2廣度優(yōu)先搜索采用隊列Bfn表示訪問順序算法復雜度2.1無向圖廣度優(yōu)先搜索無向圖的邊根據(jù)深度優(yōu)先搜索可分成兩類2.1無向圖廣度優(yōu)先搜索：例子2.2有向圖廣度優(yōu)先搜索2.2有向圖廣度優(yōu)先搜索為什么有向圖的BFS中不會出現(xiàn)前向邊1.前向邊(Forwardedges)－在迄今為止所構(gòu)建的搜索生成樹中，w是v的后裔，并且在探測(v,w)時，w已經(jīng)被標記為”visited”,則(v,w)為前向邊。2.既然要w是v的后裔，那么可以斷定，w所在層較v所在的層要低；另一方面，廣度優(yōu)先搜索生成樹是逐層產(chǎn)生的，即后裔頂點總是在祖先頂點之后訪問2.3有向圖廣度優(yōu)先搜索：應用假設(shè)目前需要對節(jié)點v的鄰節(jié)點實行入隊列，則這些要進入隊列的節(jié)點的最短距離(設(shè)w.dist)就是節(jié)點v的最短距離(設(shè)v.dist)加1，即w.dist=v.dist+1

算法復雜度主要內(nèi)容深度優(yōu)先搜索廣度優(yōu)先搜索單源最短路徑多源最短路徑3單源最短路徑3.1單源最短路徑：Dijkstra算法3.1單源最短路徑：Dijkstra算法在此算法中，設(shè)置兩個集合X和Y，其中X用于存放已經(jīng)加入到樹中的節(jié)點，Y用于存放還未加入到樹中的節(jié)點每個節(jié)點設(shè)置兩個屬性v.dist和v.prev

用于存放源節(jié)點到此節(jié)點的路徑長度(一旦此節(jié)點加入到樹中，此長度為最短距離)和此節(jié)點的在樹中的父節(jié)點(用于最短路徑計算)采用堆，復雜度為：3.1Dijkstra算法：例子3.1Dijkstra算法3.1Dijkstra算法3.1Dijkstra算法3.2Bellman-ford

算法當圖中存在權(quán)重為負的環(huán)時，某些點之間就不存在最短路徑，而Dijkstra算法是無法得出不存在最短路徑結(jié)果的Bellman-Ford算法當圖存在最短路徑，算法返回最短路徑，否則，返回false松弛操作

3.2Bellman-ford

算法3.2Bellman-ford

算法Bellman-Ford算法3.2Bellman-ford

算法算法中第一個for循環(huán)(語句4)共執(zhí)行了n?1次，嵌套內(nèi)的for循環(huán)(語句5，松弛操作)共執(zhí)行了m次，所以復雜度為O(nm)。第二個for循環(huán)(語句11)共執(zhí)行了m次?？倧碗s度為O(nm)3.2Bellman-ford

算法：例子3.2Bellman-ford

算法：例子3.3

SPFA

算法SPFA算法全稱是最短路徑快速算法(ShortestPathFasterAlgorithm)，它是對Bellman-Ford算法的改進在每輪松弛的過程中，我們保留那些d值更新過的節(jié)點，而在下一次松弛時，僅僅需要對這些節(jié)點為起始節(jié)點的邊進行松弛即可3.3SPFA

算法算法開始時，先將節(jié)點v0

進入隊列每次從隊列中取一個節(jié)點(語句6)，并對這個節(jié)點為起始節(jié)點的所有邊進行松弛在松弛的過程中，如果對應的節(jié)點d值發(fā)生改變，且節(jié)點并不在隊列中，則此節(jié)點進入隊列(語句8到11)節(jié)點進入隊列的次數(shù)達到n次，說明節(jié)點被松弛過n次，算法返回False，說明圖G存在權(quán)重為負的環(huán)。3.3SPFA

算法復雜度：SPFA算法在最壞的情況是和Bellman-Ford算法一樣的，也就是O(mn)。SPFA算法最好的情況為Ω(n)設(shè)圖為隨機圖形，則任意節(jié)點相連邊的條數(shù)的平均值為m/n(也就是算法for循環(huán)執(zhí)行m/n

次)，每個節(jié)點進入隊列的平均值為k次(k是一個常數(shù)，在稀疏圖中小于2)，即while循環(huán)執(zhí)行kn次，所以算法的平均復雜度為O(m/n?kn)=O(