《算法設(shè)計(jì)與分析》課件 第1章 概述

算法設(shè)計(jì)與分析參考書算法導(dǎo)論（原書第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í)，播放歌曲，否則不播放?？臻g復(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),UN