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

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

1.6

1.11

1.13

1.16

1.23

1.261.31

1.35

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

j/2

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

i/2

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

i/2

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

n/2

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

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

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

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

j/2

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

i/2

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

i/2

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

n/2

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

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

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

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

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

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

輸入：n(n=2k

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

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

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

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

哪6個(gè)點(diǎn)？在y軸上投影，相鄰的8個(gè)點(diǎn)

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

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

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

0-1背包問(wèn)題3

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

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

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

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

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

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

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

到cn-1

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

和c1c3c2c4...cn

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

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

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

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

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

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

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

和yi

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

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

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

≠yj

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

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

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

最小生成樹(shù)3

最小生成樹(shù)3

最小生成樹(shù)3

最小生成樹(shù)：Prim算法3

最小生成樹(shù)：Prim算法3

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

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

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

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

f(6,6)訪問(wèn)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é)點(diǎn))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é)點(diǎn)),h(8,1)(關(guān)節(jié)點(diǎn)),h(7,1),a(1,1)decbaghijkf1.3圖的回路判斷問(wèn)題：若G=(V,E)為一個(gè)有n個(gè)頂點(diǎn)和m條邊的有向或是無(wú)向圖。要測(cè)試G中是否包含有一個(gè)回路。方法：對(duì)G施加深度優(yōu)先搜索，如果探測(cè)到一個(gè)回邊，那么可以判定G中含有回路；否則G中無(wú)回路。注意：如果G是連通的無(wú)向圖，則不需要對(duì)G進(jìn)行深度優(yōu)先搜索來(lái)判定是否有回路。G無(wú)回路，當(dāng)且僅當(dāng)|E|=|V|-1。1.3拓?fù)渑判蚪o定一個(gè)有向無(wú)回路圖(DirectedAcyclicGraph,DAG)G=(V,E)。拓?fù)渑判蚴菫榱苏业綀D頂點(diǎn)的一個(gè)線性序，使得：如果(v,w)∈E,那么，在線性序中，v在w之前出現(xiàn)。我們假設(shè)在DAG中只有唯一一個(gè)入度為0的頂點(diǎn)；如果有一個(gè)以上的頂點(diǎn)入度為0，可以通過(guò)添加一個(gè)新的頂點(diǎn)s，然后將s指向所有入度為0的頂點(diǎn)，這樣s就成為唯一一個(gè)入度為0的頂點(diǎn)。decbafgabdcefg1.3拓?fù)渑判蛲負(fù)渑判虻膶?shí)現(xiàn)：從入度為0的頂點(diǎn)開(kāi)始，對(duì)DAG實(shí)施深度優(yōu)先搜索。遍歷完成后，計(jì)數(shù)器postdfn恰好對(duì)應(yīng)于一個(gè)在DAG中頂點(diǎn)的反拓?fù)湫虻玫酵負(fù)湫颍涸贒FS算法中恰當(dāng)位置增加輸出語(yǔ)句，然后將輸出結(jié)果反轉(zhuǎn)。在DFS算法中恰當(dāng)位置增加頂點(diǎn)入棧操作，然后依次取棧頂元素輸出。1.3拓?fù)渑判騞ecbafgdecbafgssdcbafge86735214abcedfg1.3

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

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

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

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

3.2Bellman-ford

算法3.2Bellman-ford

算法Bellman-Ford算法3.2Bellman-ford

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

算法：例子3.2Bellman-ford

算法：例子3.3

SPFA

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

算法算法開(kāi)始時(shí)，先將節(jié)點(diǎn)v0

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

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

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