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

1.6

1.11

1.13

1.16

1.23

1.261.31

1.35

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

j/2

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

i/2

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

i/2

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

n/2

)，其鍵值小于兒子節點的鍵值,即key(a[i])<key(a[2i])或key(a[i]<key(a[2i+1])(如果右兒子存在)，違背了堆特性，需要進行調整。調整方法：下移。沿著從a[i]到子節點(可能不唯一，則取其鍵值較大者)的路徑，比較a[i]與子節點的鍵值，若key(a[i])<max(a[2i],a[2i+1])則交換之。這一過程直到葉子節點或滿足堆特性為止。3.1堆(Heap)：下移所需要的時間是O(logn).3.1堆(Heap)：插入思路：先將x添加到a[]的末尾，然后利用Sift-up，調整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)：構建方法1：從一個空堆開始，逐步插入A中的每個元素，直到A中所有元素都被轉移到堆中。時間復雜度為O(nlogn)因為插入一個元素需要logn，總共需要插入n個元素3.1堆(Heap)：構建其他方法：直接對數據進行調整自上而下的調整一次調整需要O(nlogn)，總共需要log

n次調整，總復雜度為O(nlog2n)3.1堆(Heap)：構建自下而上的調整調整一次即可（對以節點i為根的子樹進行調整）但復雜度依然是O(nlogn)優化：1.葉子節點不需要調整；2.對子樹進行調整第i層的節點的調整最多交換?logn??i次3.1堆(Heap)：構建例：給定數組A[1…10]={5,15,19,12,6,10,7,36,11,8，9,16}，構建堆3.1堆(Heap)：構建3.1堆(Heap)：構建復雜度3.1堆(Heap)：構建復雜度3.1堆(Heap)：d堆d堆：如三叉堆，四叉堆；樹的層數為logdn3.2不相交集在離散數學我們學過等價類是對集合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的兩個集合合并，重命名。執行合并UNION(x,y)時，首先依據x找到root(x),記為u,依據y找到root(y)，記為v；然后，將u指向v。3.2不相交集：查找、合并3.2不相交集：秩和基于秩的合并按秩合并的順序決定了樹的高度。一個有n節點，且是通過不相交集合并操作形成的樹，其最大的高度是多少？3.2不相交集：秩和基于秩的合并3.2不相交集：秩和基于秩的合并3.2不相交集是不是通過基于秩的合并就總能得到最優的不相交集?不一定：如有4個節點，先合并1和2，再合并3和4，不一定是最優的如何優化？合并時調整：復雜度從O(logn)變為O(n)專門設置一個調整操作：也為O(n)部分解決方案：路徑壓縮3.2不相交集：路徑壓縮這個算法中為什么不對rank進行改變？345例：初始狀態：{1},{2},…,{9}612789執行合并序列：UNION(1,2),UNION(3,4),UN