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

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

j/2

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

i/2

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

i/2

])，則二者進(jìn)行交換，直到a[i]到達(dá)合適位置。3.1堆(Heap)：上移所需要的時間是O(logn).3.1堆(Heap)：下移假如某個內(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])則交換之。這一過程直到葉子節(jié)點(diǎn)或滿足堆特性為止。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)移到堆中。時間復(fù)雜度為O(nlogn)因?yàn)椴迦胍粋€元素需要logn，總共需要插入n個元素3.1堆(Heap)：構(gòu)建其他方法：直接對數(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)整一次即可（對以節(jié)點(diǎn)i為根的子樹進(jìn)行調(diào)整）但復(fù)雜度依然是O(nlogn)優(yōu)化：1.葉子節(jié)點(diǎn)不需要調(diào)整；2.對子樹進(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ù)為logdn3.2不相交集在離散數(shù)學(xué)我們學(xué)過等價類是對集合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é)點(diǎn)，且是通過不相交集合并操作形成的樹，其最大的高度是多少？3.2不相交集：秩和基于秩的合并3.2不相交集：秩和基于秩的合并3.2不相交集是不是通過基于秩的合并就總能得到最優(yōu)的不相交集?不一定：如有4個節(jié)點(diǎn)，先合并1和2，再合并3和4，不一定是最優(yōu)的如何優(yōu)化？合并時調(diào)整：復(fù)雜度從O(logn)變?yōu)镺(n)專門設(shè)置一個調(diào)整操作：也為O(n)部分解決方案：路徑壓縮3.2不相交集：路徑壓縮這個算法中為什么不對rank進(jìn)行改變？345例：初始狀態(tài)：{1},{2},…,{9}612789執(zhí)行合并序列：UNION(1,2),UNION(3,4),UN