算法設(shè)計與分析：數(shù)學(xué)基礎(chǔ)與數(shù)據(jù)結(jié)構(gòu)

2數(shù)學(xué)基礎(chǔ)與數(shù)據(jù)結(jié)構(gòu)2數(shù)學(xué)基礎(chǔ)與數(shù)據(jù)結(jié)構(gòu)集合、關(guān)系和函數(shù)求和計算遞歸方程求解(*)基本數(shù)據(jù)結(jié)構(gòu)(*)遞歸方程求解常系數(shù)線性同質(zhì)遞歸方程(linearhomogeneouswithconstantcoefficients)幾類特殊的非同質(zhì)遞歸方程求解常系數(shù)線性同質(zhì)遞歸方程稱為k階常系數(shù)線性同質(zhì)遞歸方程。其特征方程(characteristicequation)為：我們僅僅關(guān)注一階和二階同質(zhì)方程，因為對于使用此類遞歸方程來分析算法，往往是一階或二階的。對于一階情形，求解過程非常直觀(直接遞推)：對于二階情形，特征方程變?yōu)椋涸O(shè)該二次方程(quadraticequation)的兩個根為：。那么可以表示為：然后利用初始值：及,使用待定系數(shù)法解出系數(shù)即可。例：已知并且解：特征方程為例：已知并且解：特征方程為非同質(zhì)遞歸方程的求解？解：令已知。且例：解：這里MasterTheorem幾個例子數(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è)計之父”之美譽。本章我們將回顧幾種重要的數(shù)據(jù)結(jié)構(gòu)，包括二叉樹、堆、不相交集。堆(Heap)在許多算法中，需要大量用到如下兩種操作：插入元素和尋找最大(小)值元素。為了提高這兩種運算的效率，必須使用恰當?shù)臄?shù)據(jù)結(jié)構(gòu)。普通隊列：易插入元素，但求最大值元素需要搜索整個隊列。排序數(shù)組：易找到最大值，但插入元素需要移動大量元素。堆則是一種有效實現(xiàn)上述兩種運算的簡單數(shù)據(jù)結(jié)構(gòu)。堆的定義：堆是一個幾乎完全的二叉樹，每個節(jié)點都滿足這樣的特性：任一父節(jié)點的鍵值(key)不小于子節(jié)點的鍵值。2017910114537512345678910有n個節(jié)點的堆T,可以用一個數(shù)組H[1…n]用下面的方式來表示：T的根節(jié)點存儲在H[1]中假設(shè)T的節(jié)點x存儲在H[j]中，那么，它的左右子節(jié)點分別存放在H[2j]及H[2j+1]中(如果有的話)。H[j]的父節(jié)點如果不是根節(jié)點，則存儲在H[

j/2

]中。

觀察結(jié)論：根節(jié)點鍵值最大，葉子節(jié)點鍵值較小。從根到葉子，鍵值以非升序排列。節(jié)點的左右兒子節(jié)點鍵值并無順序要求。堆的數(shù)組表示呈“基本有序”狀態(tài)。相應(yīng)地，并非節(jié)點的高度越高，鍵值就越大。堆的基本操作make-heap(A):從數(shù)組A創(chuàng)建堆insert(H,x):插入元素x到堆H中delete(H,i):刪除堆H的第i項delete-max(H):從非空堆H中刪除最大鍵值并返回數(shù)據(jù)項輔助運算Sift-up若某個節(jié)點H[i]鍵值大于其父節(jié)點的鍵值，就違背了堆的特性，需要進行調(diào)整。調(diào)整方法：上移。沿著H[i]到根節(jié)點的唯一一條路徑，將H[i]移動到合適的位置上：比較H[i]及其父節(jié)點H[

i/2

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

i/2

])，則二者進行交換，直到H[i]到達合適位置。過程Sift-up(H,i)輸入：數(shù)組H[1…n]，索引1

i

n輸出：上移H[i](如果需要)，使它的鍵值不大于父節(jié)點的鍵值1.done←false2.ifi=1thenexit{根節(jié)點}3.repeat4.ifkey(H[i])>key(H[

n/2

])then互換H[i]和H[i/2

]5.elsedone←true{調(diào)整過程至此已經(jīng)滿足要求，可退出}6.i←

i/2

7.untili=1ordone{調(diào)整進行到根節(jié)點，或到某一節(jié)點終止}輔助運算Sift-down假如某個內(nèi)部節(jié)點H[i](i≤

n/2

)，其鍵值小于兒子節(jié)點的鍵值,即key(H[i])<key(H[2i])或key(H[i]<key(H[2i+1])(如果右兒子存在)，違背了堆特性，需要進行調(diào)整。調(diào)整方法：下滲。沿著從H[i]到子節(jié)點(可能不唯一，則取其鍵值較大者)的路徑，比較H[i]與子節(jié)點的鍵值，若key(H[i])<max(H[2i],H[2i+1])則交換之。這一過程直到葉子節(jié)點或滿足堆特性為止。過程

Sift-down(H,i)輸入：數(shù)組H[1…n]，索引1

i

n輸出：下滲H[i](若它違背了堆特性)，使H滿足堆特性1.done←false2.if2i>n,thenexit{葉子節(jié)點，無須進行}3.repeat4.i←2i5.ifi+1<nandkey(H(i+1))>key(H(i))theni=i+1//有右兒子6.ifkey(H[

i/2

])<key(H[i])then互換H[i]和H[

i/2

]7.elsedone←true{調(diào)整過程至此已經(jīng)滿足堆特性，可退出}8.endif9.until2i>nordone{調(diào)整進行到葉節(jié)點，或到某一節(jié)點終止}操作insert(H,x):插入元素x到堆H中思路：先將x添加到H的末尾，然后利用Sift-up，調(diào)整x在H中的位置，直到滿足堆特性。輸入：堆H[1…n]和元素x輸出：新堆H[1…n+1]，x是其中元素之一。1.n←n+1{堆大小增1}2.H[n]←x;3.Sift-up(H,n){調(diào)整堆}樹的高度為

logn,所以將一個元素插入大小為n的堆所需要的時間是O(logn).操作delete(H,i)思路：先用H[n]取代H[i]，然后對H[i]作Sift-up或Sift-down)，直到滿足堆特性。輸入：非空堆H[1…n]，索引i，1≤i≤n.輸出：刪除H[i]之后的新堆H[1…n-1].1.x←H[i];y←H[n];2.n←n-1;{堆大小減1}3.ifi=n+1thenexit{要刪除的剛好是最后一個元素，葉節(jié)點}4.H[i]←y;{用原來的H[n]取代H[i]}5.ifkey(y)

key(x)thenSift-up(H,i)6.elseSift-down(H,i);7.endif所需要的時間是O(logn).操作delete-max(H)輸入：堆H[1…n]輸出：返回最大鍵值元素，并將其從堆中刪除

x←H[1]2.delete(H,1)3.returnxmake-heap(A):從數(shù)組A創(chuàng)建堆方法1：從一個空堆開始，逐步插入A中的每個元素，知道A中所有元素都被轉(zhuǎn)移到堆中。時間復(fù)雜度為O(nlogn).為什么？方法2：MAKEHEAP(創(chuàng)建堆)輸入：數(shù)組A[1…n]輸出：將A[1…n]轉(zhuǎn)換成堆1.fori←

n/2

downto12.Sift-down(A,i){使以A[i]為根節(jié)點的子樹調(diào)整成為堆，故調(diào)用down過程}3.endfor例：給定數(shù)組A[1…10]={4,3,8,10,11,13,7,30,17,26}復(fù)雜度分析樹高k=

logn

，第i層正好2i個節(jié)點,0

i<k,(不含最深的葉子節(jié)點層),每個節(jié)點的down過程最多執(zhí)行k-i次,故down過程執(zhí)行次數(shù)上限為時間復(fù)雜度為O(n).不相交集(DisjointSets)假設(shè)有n個元素，被分成若干個集合。例如S={1,2,…11}分成4個子集1:{1,7,10,11}，3:{2,3,5,6}，8:{4,8}，9:{9}并分別命名。事實上，每個子集可以用樹表示，除根節(jié)點外，每個節(jié)點都有指針指向父節(jié)點。上例可以用樹表示為:1111072653984假如要執(zhí)行如下計算任務(wù)：FIND(x):尋找包含元素x的集合的名字UNION(x,y):將包含元素x和y的兩個集合合并，重命名。記root(x)為包含元素x的樹的根，則FIND(x)返回root(x).執(zhí)行合并UNION(x,y)時，首先依據(jù)x找到root(x),記為u,依據(jù)y找到root(y)，記為v；然后，將u指向v。優(yōu)點：簡單明了缺點：多次合并后，樹高度可能很大，查找困難。12n-1…例：初始狀態(tài)：{1},{2},…,{n}執(zhí)行合并序列：UNION(1,2),UNION(2,3),…UNION(n-1,n).我們得到的結(jié)果是：n12n-1…n執(zhí)行查找序列：FIND(1),FIND(2),…,FIND(N).需要比較的次數(shù)是：目標：降低樹的高度。措施：RankHeuristic。1.給每個樹的根節(jié)點定義一個秩(rank)，表示該樹的高度。2.在執(zhí)行UNION(x,y)，首先找到u=root(x)，v=root(y)。3.然后比較rank(u)和rank(v)

若rank(u)=rank(v)，則使u指向v，v成為u的父親，同時rank(v)+1

若rank(u)<rank(v)，則使u指向v，v成為u的父親若rank(u)>rank(v)，則使v指向u，u成為v的父親123n…Algorithm:UNION輸入：兩個元素x,y.輸出：將包含x,y的兩棵樹合并1.u←FIND(x);v←FIND(y)2.ifrank(u)≤rank(v)then//RankHeuristic3.p(u)←v4.ifrank(u)=rank(v)thenrank(v)=rank(v)+15.elsep(v)←u6.endif目標：進一步提高FIND的操作的性能。措施：在執(zhí)行FIND操作時，同時進行路徑壓縮(Pathcompression)。1267執(zhí)行FIND(7)同時進行路徑壓縮1267Algorithm:FIND輸入：節(jié)點x輸出：root(x)和路徑壓縮后的樹1.y←x2.whilep(y)≠null{尋找包含x的樹的根}3.y←p(y)4.endwhile5.root←y;y←x{重新賦值為原來的節(jié)點x}6.whilep(y)≠null{執(zhí)行路徑壓縮}7.w←p(y){父節(jié)點暫存為w}8.p(y)←root{該路徑上的節(jié)點直接指向根節(jié)點}9.y←w{繼續(xù)下一步壓縮}10.endwhile11.returnroot345例：初始狀態(tài)：{1},{2},…,{9}612789執(zhí)行合并序列：UNION(1,2),UNION(3,4),UNION(5,6),UN