算法導(dǎo)論復(fù)習(xí)大綱DOC

1、算法設(shè)計(jì)與分析復(fù)習(xí)提綱 2014.7.51 引言(ch1)1. 什么是算法及其特征算法（Algorithm）是通過一個(gè)有限的指令序列集合對特定問題進(jìn)行求解的一種計(jì)算執(zhí)行描述。算法特征：（1）輸入：一個(gè)算法具有零個(gè)或多個(gè)取自指定集合的輸入值；（2）輸出：對每一次輸入，算法具有一個(gè)或多個(gè)與輸入值相聯(lián)系的輸出值；（3）確定性：算法的每一個(gè)指令步驟都是明確的；（4）有限性：對每一次輸入，算法都必須在有限步驟（即有限時(shí)間）內(nèi)結(jié)束；（5）正確性：對每一次輸入，算法應(yīng)產(chǎn)生出正確的輸出值；（6）通用性：算法的執(zhí)行過程可用于所有同類求解問題，而不僅適用于特殊輸入。2.問題實(shí)例和問題規(guī)模問題實(shí)例是指需要計(jì)算同一個(gè)

2、結(jié)果的問題的所有輸入。問題規(guī)模是指輸入實(shí)例的大小,而輸入實(shí)例是指問題的具體計(jì)算例子2 算法初步(ch2)1. 插入排序算法1）算法步驟：從左到右掃描數(shù)據(jù)A，掃描到一個(gè)元素，將Aj與其左邊的元素從右到左依次比較，若比之小，則將其之前元素后移，插入A【j】,直至A【j】比他前面的元素大，掃描A中的下一個(gè)元素2）偽代碼：InsertSort(A)for j=2 to A.length /第一層循環(huán)Key=Aji=j-1While i0 and aikey /第二層循環(huán)Ai+1=Aii=i-1Ai+1=key 2.算法復(fù)雜性及其度量 (1)時(shí)間復(fù)雜性和空間復(fù)雜性； (2)最壞、最好和平均情形復(fù)雜性；順

3、序情況下B（n）=O（n）、倒序情況下W（n）=O（n2）、A（n）=O(n2)W(n)空間復(fù)雜性：需要常數(shù)個(gè)額外的臨時(shí)空間存儲臨時(shí)數(shù)據(jù)2. 插入排序的最壞、最好和平均時(shí)間最壞O(n2)、最好O(n)和平均時(shí)間O(n2),空間復(fù)雜度是O(1)，穩(wěn)定排序3. 歸并排序算法及其時(shí)間復(fù)雜性時(shí)間（n log n）1）算法步驟分解：分解待排序的n個(gè)元素的序列為各具n/2個(gè)元素的兩個(gè)子序列解決：適用歸并排序遞歸的排序2個(gè)子序列合并：從左到有遍歷2個(gè)子序列，比較最前面的元素，將較小的元素移出子序列 合并到上級序列的末尾，循環(huán)進(jìn)行上2步，直接所有元素都被合并到上級序列，公進(jìn)行r-p+1次；2）偽代碼：MERG

4、E-SORT(A,p,r) if prq=向下取整（p+r）/2MERGE-SORT(A,p,q);MERGE-SORT(A,q+1,r)MERGE(A,p,q,r)MERGE(A,p,q,r)N1=q-p+1N2=r-q將A拆成長度分別為N1、n2的2個(gè)子數(shù)組L,RL,R的末尾元素的后一個(gè)元素取值無窮大，作為哨兵；i=1，j=1for k=p to r if Li=RjAk=Lii=i+1elseAk=Rjj=j+1 3函數(shù)增長率(ch3)1. 漸近記號O、的定義及其使用1） O漸進(jìn)上界：0=f(n), f(n)的階小與g(n)的階2）漸進(jìn)下界：0=C(g(n) , f(n)的階大與g(n)

5、的階3）漸緊界：0=C1(g(n) =f(n) , f(n)的階與g(n)的階相等2. 標(biāo)準(zhǔn)復(fù)雜性函數(shù)及其大小關(guān)系（1） 多項(xiàng)式時(shí)間階的大小O(1) O(log n) O(n) O(n*log n) O(n) O(n3)（2） 指數(shù)時(shí)間階的大小O(2n) O(n!) 證明2）對象限界最大最小項(xiàng)限界；幾何級數(shù)限界；3）和式分解簡單的一分為二；更復(fù)雜的劃分；積分近似；4）Knuth求和：使用數(shù)學(xué)歸納法；使用攝動法；使用遞歸；使用積分；使用二重求和；使用有限演算；使用母函數(shù)。4 遞歸關(guān)系式(ch4)1.替換法(1)猜測解數(shù)學(xué)歸納法證明；T（n）=2T(n/2)+n 猜：T（n）= O(nlogn)證

6、: 2T(n/2)+n=Cnlogn 帶入計(jì)算(2)變量變換法；T（n）=2T(n1/2)+log n令m= logn,則，n=2mT(2m)=2T(2m -1/2)+m ，令S（m）=T(2m)則：S(m)=2Sm/2+m類似T（n）=2T(n/2)+n=O(m log m)=O(logn log log n)2.迭代法(1)展開法；T(1)=O(1)T（n）=3T(n/4)+n=n+3n/4+32n/42+3KT(n/4K)總有K，使得1=n/4K=2,即K=1,b=1整數(shù)Case1 f(n)= O(n logba-) = C n logba- 則：T(n)= （n log b a）Cas

7、e2 f(n)= C n logba+ 且：af(n/b)=cf(n),對于常數(shù)C=1和足夠大的n成立，則T(n)= （f(n)）5 堆排序(ch6)1堆的概念和存儲結(jié)構(gòu)堆是一種數(shù)據(jù)結(jié)構(gòu)，堆是一個(gè)數(shù)組，近似完全二叉樹，除最底層外，全部從左到右填充滿，對于序號為i的結(jié)點(diǎn)，其父結(jié)點(diǎn)的序號為i/2,其左孩子的序號為2i,其右孩子序號為2i+1;0=A.heap-size=A.length n個(gè)元素的序列k1,k2,ki,kn當(dāng)且僅當(dāng)滿足下關(guān)系時(shí)，稱之為堆。(ki= k2i,ki= k2i,ki= k2i+1), (i = 1,2,3,4.n/2)l 堆的性質(zhì)和種類大根堆：除根結(jié)點(diǎn)外，所有結(jié)點(diǎn)小于其父

8、結(jié)點(diǎn)；用于堆排序、收益問題。小根堆：除根結(jié)點(diǎn)外，父結(jié)點(diǎn)小于其所有結(jié)點(diǎn)；用于優(yōu)先隊(duì)列；成本問題；l 堆的操作：建堆；整堆；1)整堆算法：假設(shè)i的左右子樹已經(jīng)是大根堆,對i結(jié)點(diǎn)進(jìn)行整堆，使其也是大根堆對調(diào)整的子樹結(jié)點(diǎn)循環(huán)進(jìn)行上2步驟，將小元素逐級下沉，直至滿足堆特性；整堆時(shí)間復(fù)雜度 O（log n）2)整堆偽代碼Max-heapify(A,i) l=left(i)r=right(i)if lAilargest=lelse largest=iif rAilargest=rif largestiexchange ai with largestmax-heapify(A,largest)3)建堆算法因?yàn)?/p>

9、從A.heap-size/2+1起到A.heapsize，都是葉子結(jié)點(diǎn)，故建堆可從A.heap-size/2起到1整堆實(shí)現(xiàn)；算法復(fù)雜度O（n）4)建堆偽代碼Bulid_max_heap(A)heap-size=A.lengthfor i= A.heap-size /2 to 1Max-heapify(A,i)l 堆排序算法和時(shí)間復(fù)雜性算法思想：1）將數(shù)組建堆2）將根元素與結(jié)點(diǎn)n交換并縮減堆的長度13）對首元素整堆4）重復(fù)上述3個(gè)步驟，直至堆大小為1（i=2時(shí)進(jìn)行最后一次重復(fù)操作）時(shí)間復(fù)雜度O（n lg n）偽代碼Heapsize(A) build_max_heap(A) For i=A.len

10、gth to 2 Exchange A1 to Ai A.heap-size=A.heap-size-1 max-heapfly(A,1)l 優(yōu)先隊(duì)列及其維護(hù)操作優(yōu)先隊(duì)列是維護(hù)集合S的數(shù)據(jù)結(jié)構(gòu)，每個(gè)元素具有一個(gè)關(guān)鍵字key；用于分支限界、搜索算法。支持如下操作：a) 插入 insert(S,x) 算法思想：1）將元素插入末尾Size+1的位置2）從插入位置自底而上調(diào)整，使之滿足堆性質(zhì)算法復(fù)雜度 O（log n）b) 取最大關(guān)鍵字Maximum(S)算法思想，輸出優(yōu)先級最大的，也就是堆的根元素；c)刪除并返回最大鍵值的元素 Extract-max(S)算法思想：1） 取堆根2） A1-Aheap

11、-sizeA3） heap-sizeA4） 對A1整堆時(shí)間復(fù)雜度O（log n）d) 增值 元素x的關(guān)鍵字增加到k Increase-Key(S,x,k)算法思想：1）如果Ai的關(guān)鍵字大于K，則對i進(jìn)行整堆；2）否則，若i不是根結(jié)點(diǎn)且K大于Ai的父結(jié)點(diǎn)，則交換Ai與其父結(jié)點(diǎn)的關(guān)鍵字，并將K值賦予其父結(jié)點(diǎn)。時(shí)間復(fù)雜度O（log n）6 快速排序(ch7)1. 快速排序算法及其最好、最壞時(shí)間和平均時(shí)間快排采用分治法的思想，最好O(nlogn),最壞O(n2),平均O(nlogn)（1）分治法的基本思想 分治法的基本思想是：將原問題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，

12、然后將這些子問題的解組合為原問題的解。（2）快速排序的基本思想 設(shè)當(dāng)前待排序的無序區(qū)為Rlow.high，利用分治法可將快速排序的基本思想描述為：分解： 在Rlow.high中任選一個(gè)記錄作為基準(zhǔn)(Pivot)，以此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左、右兩個(gè)較小的子區(qū)間Rlow.pivotpos-1)和Rpivotpos+1.high，并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為pivot)的關(guān)鍵字pivot.key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot.key，而基準(zhǔn)記錄pivot則位于正確的位置(pivotpos)上，它無須參加后續(xù)的排序。Ap.r被劃分為倆個(gè)（可能空）

13、的子數(shù)組Ap .q-1和Aq+1 .r，使得Ap .q-1 = Aq = Aq+1 .r求解：通過遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間Rlow.pivotpos-1和Rpivotpos+1.high快速排序。3合并/快速排序void quick_sort(int s, int l, int r) if (l r) int i = l, j = r, x = sl; while (i j) while(i = x) / 從右向左找第一個(gè)小于x的數(shù) j-; if(i j) si+ = sj; while(i j & si x) / 從左向右找第一個(gè)大于等于x的數(shù) i+; if(i j) sj- = si

14、; si = x; quick_sort(s, l, i - 1); / 遞歸調(diào)用 quick_sort(s, i + 1, r); 2.隨機(jī)快速排序算法及其期望時(shí)間期望時(shí)間負(fù)責(zé)度O(nlogn)算法描述：分解：以ap為基準(zhǔn)元素將ap:r劃分為3段ap:q-1,aq和aq+1:r,使 ap:q-1中任何一個(gè)元素小于等于aq，而aq+1:r中任何一個(gè)元素大于等于aq。下標(biāo)q在劃分過程中確定。遞歸求解：通過遞歸調(diào)用快速排序算法分別對ap:q-1和aq+1:r進(jìn)行排序。合并：由于對ap:q-1和aq+1:r的排序是就地進(jìn)行的，所以在ap:q-1和aq+1:r都已排好的序后，不需要執(zhí)行任何計(jì)算，ap:

15、r就已排好void RandomizedQuickSort(double *a,int begin,int end) /隨機(jī)化快速排序 if(beginend) int p = RandomizedPartition(a,begin,end); RandomizedQuickSort(a,begin,p-1); RandomizedQuickSort(a,p+1,end); intRandomizedPartition(double*a,intbegin,intend) inti=Random(begin,end);doubletemp=aend;aend=ai;ai=temp; return

16、Partition(a,begin,end);int Random（int m,int n） /產(chǎn)生一個(gè)隨機(jī)下表，用其對應(yīng)的數(shù)組元素作為比較標(biāo)準(zhǔn)srand(unsigned)time(NULL);return m+(rand()%(n-m+1);int Partition(double *a,intbegin,int end) int i = begin-1,j=begin; double x = aend; while(jend) if(ajB小于或等于Ai的元素?cái)?shù)目主要要解決的問題： 計(jì)數(shù)：統(tǒng)計(jì)小于或等于 統(tǒng)計(jì)小于或等于Ai的元素?cái)?shù)目 值相同元素的處理一種特殊情形的計(jì)數(shù)排序：問題：n個(gè)互不

17、相同的整數(shù)A1.n，1Ain，i=1n排序算法：SpecialCountingSort(A,B)/B1.n為排序結(jié)果for i1 to n do BAiAi; /如Ai=5，就放到B5中時(shí)間：O(n) ，無比較一般情形的計(jì)數(shù)排序：問題：n個(gè)可以相同的整數(shù)A1.n，1Aik，i=1n，這里k是Ai的取值范圍，不一定為n。基本思想：步驟：A1.n計(jì)數(shù)器C1.kB1.n Step 1(值相同元素的計(jì)數(shù) 值相同元素的計(jì)數(shù))：將A中的值為i的元素個(gè)數(shù)記入Ci中； Step 2(累計(jì)計(jì)數(shù))：對C1.k進(jìn)行修改，使得Ci的值表示為i的元素個(gè)數(shù)； Step 3(放置)：將Aj依據(jù)C Aj，放入正確位置BCAj

18、上，并修改CAj CAj-1；算法：CountingSort(A,B,k)/ B1.n為排序結(jié)果，C1.k為計(jì)數(shù)數(shù)組for i1 to k do Ci0;for j1 to lengthA do / 掃描A，值相同元素計(jì)數(shù) 值相同元素計(jì)數(shù)CAj+; for i2 to k do / Ci修改，累計(jì)計(jì)數(shù)CiCi+Ci-1; for jlengthA downto 1 do BCAjAj; CAj-; 時(shí)間：T(n k)=(n+k)=(n) 如果k=(n)時(shí)3. 基數(shù)排序適應(yīng)的排序?qū)ο蟆⑺惴ê蜁r(shí)間假定A1.n是非負(fù)整數(shù)，用k進(jìn)制表示為不超過d位數(shù)。l算法：RadixSort(A d) RadixS

19、ort(A,d) for i1 to d do使用穩(wěn)定的排序算法對 使用穩(wěn)定的排序算法對A的第i位排序；/如計(jì)數(shù)排序l時(shí)間：T(n)=(d(n+k) /k為基，d為位數(shù)=(n) /如果k=(n)且d是常數(shù)示例：引理8.3, 給定n個(gè)d位數(shù)，其中每一個(gè)數(shù)位有k個(gè)可能的取值。如果RADIX-SORT使用的穩(wěn)定排序方法耗時(shí)(n+k)，那么它就可以在(d(n+k)時(shí)間內(nèi)將這些數(shù)排好序。證明：當(dāng)每位數(shù)字都在0到k-1區(qū)間內(nèi)（這樣它就有k個(gè)可能的取值），且k的值不太大的時(shí)候，計(jì)數(shù)排序是一個(gè)好的選擇。對n個(gè)d位數(shù)來說，每一輪排序耗時(shí)(n+k)。共有d輪，因此基數(shù)排序的總時(shí)間為(d(n+k).d不為常數(shù)，基數(shù)

20、排序算法還是線性時(shí)間嗎？設(shè)n個(gè)整數(shù)的取值范圍是0nc，c是整常數(shù)，c1對于十進(jìn)制整數(shù)，nc需要的位數(shù)d=log10nc+1log10nT(n)=(d(n+k) =(nlogn) /k為10因此，不是線性時(shí)間排序l算法何時(shí)為線性時(shí)間？Idea: 只要使d變?yōu)槌?shù)，k變大到與n同階How to do How to do : 選基k=n，則nc的位數(shù)為lognnc=c=dd=c， k=nT(n)=(n)4. 桶排序適應(yīng)的排序?qū)ο蟆⑺惴ê蜁r(shí)間假定：輸入是均勻分布在0,1)上的實(shí)數(shù)。l基本思想：0,1)劃分為0,1/n),1/n,2/n),k/n,(k+1)/n),(n-1)/n,1)n個(gè)大小相等的子區(qū)

21、間，每個(gè)子區(qū)間看作一個(gè)桶；將n個(gè)元分配桶中；對每個(gè)桶里的元素進(jìn)行排序，依次連接桶；輸入：0A1.n1l輔助數(shù)組：B0.n-1是一個(gè)指針數(shù)組，指向每個(gè)桶(鏈表)l關(guān)鍵字映射：由于0Ai 1，必須將Ai映射到0, 1n-1上0,1)0,n) /通過函數(shù)nAi即knA ik+1 /存在k桶號k=nAi/映射函數(shù)算法描述：BucketSort( A)nlengthA; Timefor i1 to n do /掃描A (n)將Ai插入到鏈表BnAi中;for i0 to n-1 do (n)*用插入排序?qū)i排序;將B0, B1, Bn-1連接起來;(n)注：n個(gè)數(shù)是均勻分布在0 1)中，每個(gè)桶中大約只

22、有一個(gè)數(shù)，時(shí)間為O(1)8 中位數(shù)和順序統(tǒng)計(jì)(ch9)1. 最大和最小值的求解方法最小/最大值：最壞情形W(n)=n-1次比較，時(shí)間為(n)l同時(shí)求最大、最小值 一種方法：獨(dú)立分別求，比較次數(shù)為n-1+n-2=2n-3 另一種方法：成對輸入x, y，每對比較3次比較x, y；將min(x, y)與當(dāng)前最小值比較；將max(x, y)與當(dāng)前最大值比較；總比較次數(shù)約為3n/2。/第一對元素比較一次，最后一組元素若為一個(gè)，至多比較二次2. 期望時(shí)間為線性的選擇算法基于分治法的思想：利用快排序的隨機(jī)劃分法，進(jìn)行問題的劃分具體步驟：1 劃分Ap.r = Ap.q-1AqAq+1.r； /Aq為劃分元2

23、K - q-p+1; /即Aq是第k個(gè)最小元3 If (i=k) then / k=左區(qū)間長度+1return Aq；If(ik) then 在右區(qū)間中繼續(xù)找第i-k個(gè)元素； 臨界條件：當(dāng)區(qū)間長度為1時(shí)，直接返回該元素RandomizedSelect(A, p, r, i) /選擇ith元素if p=r then return Ap; /臨界問題處理qRandomizedPartition(A, p, r); /進(jìn)行劃分并返回劃分元的下標(biāo)kq-p+1; /Aq是第k個(gè)小的元素if i=k then/Aq是ith元素return Aq;else if ik then/ith元素落在左區(qū)間retu

24、rn RandomizedSelect(A, p, q-1, i);else/ith元素落在右區(qū)間return RandomizedSelect(A, q+1, r, i-k);最好：每次劃分為相等的左右區(qū)間 T(n)=T(n/2)+n = T(n)=(n)最壞：每次劃分為不均等的左右區(qū)間T(n)=T(n-1)+n = T(n)=(n2)平均(期望)：分析略。T(n)=(n)3. 最壞時(shí)間為線性的選擇算法及其時(shí)間分析算法步驟：While n1 dostep 1.將n個(gè)元素分成5個(gè)1組，共n/5組。其中最后1組有n mod 5個(gè)元素。step 2.用插入排序?qū)γ拷M排序，取其中值。若最后1組有偶數(shù)

25、個(gè)元素，取較小的中值。step 3 .遞歸地使用本算法找找n/5個(gè)中值的中值x。step 4.用x作為劃分元對A數(shù)組進(jìn)行劃分，并設(shè)x是第k個(gè)最小元。step 5. if i=k then return x;else if i 左區(qū)間和右區(qū)間的最大長度7n/10+6運(yùn)行時(shí)間遞歸式的建立step 1 2: O(1); step 3: T(n/5);step 4: O(n);step 5: 至多T(7n/10+6)(n/5向上取整)運(yùn)行時(shí)間遞歸式的求解用替代法證：T( )n) cnT(n)c n/5+c(7n/10+6)+an /a為常數(shù)c(n/5+1)+c(7n/10+6)+an= cn/5+c+

26、7cn/10+6c+an= 9cn/10+7c+an= cn+(-cn/10+7c+an) cn/if -cn/10+7c+an0要使-cn/10+7c+an0，只要c10an/(n-70)假定n140， 有n/(n-70)2取c20a =-cn/10+7c+an0故T(n)=O(n)9 紅黑樹(ch13)1. 紅黑樹的定義和節(jié)點(diǎn)結(jié)構(gòu)Def. 1: 紅黑樹是滿足下述性質(zhì)的二叉搜索樹每個(gè)節(jié)點(diǎn)必須為紅色或黑色 每個(gè)節(jié)點(diǎn)必須為紅色或黑色； /性質(zhì)1根為黑色；/性質(zhì)2樹中的nil葉子為黑； /性質(zhì)3若節(jié)點(diǎn)為紅，則其兩個(gè)孩子必為黑；/性質(zhì)4每節(jié)點(diǎn)到其后代葉子的所有路徑含有同樣多的黑節(jié)點(diǎn)；/性質(zhì)5節(jié)點(diǎn)的結(jié)

27、構(gòu)ParentleftCorlorKeyRight2. 黑高概念Def. 2：節(jié)點(diǎn)x的黑高bh(x)是該節(jié)點(diǎn)到它的任何后代葉子路徑上的黑節(jié)點(diǎn)數(shù)(不包括x本身)Def. 3：紅黑樹的黑高是根的黑高，記bh(rootT)3. 一棵n個(gè)內(nèi)點(diǎn)的紅黑樹的高度至多是2log(n+1)先證對任何以x為根的子樹其內(nèi)節(jié)點(diǎn)數(shù)2bh(x)-1歸納基礎(chǔ)：當(dāng)bh(x)=0時(shí)，x就是nilT 2bh(x)-1= 20-1=0 即為0個(gè)內(nèi)節(jié)點(diǎn)，正確歸納假設(shè)：對x的左右孩子命題正確歸納證明：x的左右孩子的黑高或?yàn)閎h(x)或?yàn)閎h(x)-1x的內(nèi)點(diǎn)數(shù)=左孩子內(nèi)點(diǎn)數(shù)+右孩子內(nèi)點(diǎn)數(shù)+1(2bh(x)-1-1)+(2bh(x)-1

28、-1)+1= 2bh(x)-1 即第點(diǎn)得證。證明bh(rootT)h/2， h為紅黑樹的樹高紅點(diǎn)的孩子必為黑/紅黑樹的性質(zhì)4紅點(diǎn)的層數(shù)h/2因此 = bh(rootT)h/2證明最后結(jié)論紅黑樹有n個(gè)內(nèi)點(diǎn)由 = n2bh(rootT)-12h/2-1 = h2log(n+1) 4. 左旋算法(略)步驟解釋：需要變動的是3根粗鏈 臨界情形yrightx /記錄指向y節(jié)點(diǎn)的指針rightxlefty, pleftyx /連到x右 =nilTpypx, px的左或右指針指向y /y連到px Px=nilT, 即x為根Leftyx, pxy /x連到y(tǒng)左注：-要注意先后順序；-每條邊的修改涉及雙向；-要

29、考慮臨界情形(特殊情形)；LeftRotate(T, x) /假定rightx nilTy rightx; /step rightx lefty; plefty x; /step py p x; /step if px=nilT then /x是根rootT y; /修改樹指針else if x=leftpx then leftpx y; else rightpx y;lefty x; px y;/step T(n)=O(1)5. 插入算法的時(shí)間、至多使用2次旋轉(zhuǎn)step 1 ：將z節(jié)點(diǎn)按BST樹規(guī)則插入紅黑樹中，z是葉子節(jié)點(diǎn)；step 2 ：將z涂紅；step 3 ：調(diào)整使其滿足紅黑樹的性質(zhì)

30、； RBInsert(T, z) y nilT; /y用于記錄：當(dāng)前掃描節(jié)點(diǎn)的雙親節(jié)點(diǎn)x rootT; /從根開始掃描while x nilT do /查找插入位置 y x; if keyzkeyx then /z插入x的左邊x leftx;Else x rightx; /z插入x的右邊pz y; /y是z的雙親if y= nilT then /z插入空樹rootT z; /z是根elseif keyzkeyy then lefty z; /z是y的左子插入elserighty z; /z是y的右子插入leftz rightz nilT;colorzred;RBInsertFixup(T, z

31、);時(shí)間：T(n)=O(logn)調(diào)整算法的時(shí)間：O(logn);整個(gè)插入算法的時(shí)間：O(logn);調(diào)整算法中至多使用2個(gè)旋轉(zhuǎn)lRBInsertFixup(T, z) while ( colorpz=red ) do /若z為根，則pz=nilT，其顏色為黑，不進(jìn)入此循環(huán) /若pz為黑，無需調(diào)整，不進(jìn)入此循環(huán)if pz=leftppz then /case 1,2,3 y rightppz; /y是z的叔叔if colory=red then /case 1 colory=black; colorpz=black; colorppz=red; zppz;else /case 2 or cas

32、e 3 y為黑else /case 2 or case 3 y為黑 if z=rightpz then /case 2 z pz; /上溯至雙親leftRotate(T, z); /以下為case 3 colorpz=black; colorppz=red;RightRotate(T ppz); RightRotate(T, ppz); /pz為黑，退出循環(huán) /case 1s endif /case 2 or 3 s else /case 4,5,6s 與上面對稱 /end whilecolorroott black;6. 刪除算法的時(shí)間、至多使用3次旋轉(zhuǎn)RBDelete(T, z) if (

33、leftz=nilT) or (rightz=nilT) then /case 1,2y z; /后面進(jìn)行物理刪除yelse /z的兩子樹均非空，case 3 y TreeSuccessor(z); /y是z的中序后繼/此時(shí)，y統(tǒng)一地是x的雙親節(jié)點(diǎn)且是要刪除節(jié)點(diǎn) 的雙親節(jié)點(diǎn)且是要刪除節(jié)點(diǎn)/ x是待連接到py的節(jié)點(diǎn)，以下要確定xif lefty nilT then /本if語句綜合了case1,2,3的xx lefty;Elsex righty; /以下處理：用x取代y與y的雙親連接px py;if py=nilT then /y是根rootT x; /根指針指向xelse /y非根if y=l

34、eftpy then /y是雙親的左子leftpy x;elserightpy x;if yz then /case 3y的內(nèi)容copy到z;if colory=black thenRBDeleteFixup(T, x); /調(diào)整算法return y; /實(shí)際是刪除y節(jié)點(diǎn)調(diào)整算法：RBDeleteFixup(T, x)討論x：或是y的唯一孩子；或是哨兵nilT 可以想象將y的黑色涂到x上，于是-若x為紅，只要將其涂黑，調(diào)整即可終止；-若x為黑，將y的黑色涂上之后，x是一個(gè)雙黑節(jié)點(diǎn)，違反性質(zhì)1。處理步驟如下：step 1：若x是根，直接移去多余一層黑色(樹黑高減1)，終止；step 2：若x原為

35、紅，將y的黑色涂到x上，終止；step 3 ：若x非根節(jié)點(diǎn)，且為黑色，則x為雙黑。通過變色、旋轉(zhuǎn)使多余黑色向上傳播，直到某個(gè)紅色節(jié)點(diǎn)或傳到根；RB-DELETE-FIXUP(T,x) /調(diào)整算法的時(shí)間：O(logn)ehile x != T.root and x.color = BLACKif w.color = REDw.color=BLACKx.p.color=REDLEFT-ROTATE(T,x,p)if w.left.color = BLACK and w.right.color = BLACKw.color=REDx = x.pelse if w.right.color = BLAC

36、Kw.left.color = BLACKw.color = REDRIGHT-ROTATE(T,w)x.p.color = BLACKw.right.color = BLACKLEFT-ROTATE(T,x,p)x=T.rootelse(same as then clause with “right” and “l(fā)eft”exchanged)x.color = BlACK10 數(shù)據(jù)結(jié)構(gòu)的擴(kuò)張(ch14)1.動態(tài)順序統(tǒng)計(jì)：擴(kuò)展紅黑樹，支持選擇問題(給定Rank求相應(yīng)的元素)，Rank問題(求元素x在集合中的Rank)(1)節(jié)點(diǎn)結(jié)構(gòu)的擴(kuò)展；OS樹的定義：S(OrderStatistic)樹是 棵

37、紅黑樹在每個(gè) OS(Order-Statistic)樹是一棵紅黑樹在每個(gè)節(jié)點(diǎn)上擴(kuò)充一個(gè)域sizex而得到的，它是以x為根的子樹中內(nèi)部節(jié)點(diǎn)的總數(shù)(包括x) 即子樹大 根的子樹中內(nèi)部節(jié)點(diǎn)的總數(shù)(包括x)，即子樹大小。節(jié)點(diǎn)結(jié)構(gòu)：key/size(2)選擇問題的算法；選擇問題定義：在以x為根的子樹中，查找第i個(gè)最小元素算法：OSSelect(x, i) (1): r sizeleftx+1;(2): 若i=r 則返回x (2): 若i=r，則返回x；若ir，則遞歸地在x的左子樹中繼續(xù)找第i個(gè)元素；若ir，則遞歸地在x的右子樹中繼續(xù)找第i-r個(gè)元素；時(shí)間：O(logn)(3)Rank問題的算法；求秩問題

38、定義：OS樹中，給定元素x求其rank算法：step 1: 在以x為根的子樹中，x的秩：r sizeleftx+1； r sizeleftx+1；step 2: 若x是根，則返回r；若x是雙親的左子，則x在以px為根的子樹 若x是雙親的左子，則x在以px為根的子樹中的秩是r；若x是雙親的右子，則x在以px為根的子樹 p中的秩是r r+sezeleftpx+1；x上移至px；重復(fù) 直成立時(shí) 重復(fù)，直至成立時(shí)終止；時(shí)間：O(logn)(4)維護(hù)樹的成本分析；1）OS樹的維護(hù): 插入算法Phase 1：從根向下插入新節(jié)點(diǎn)將搜索路徑上所經(jīng) Phase 1：從根向下插入新節(jié)點(diǎn)，將搜索路徑上所經(jīng)歷的每個(gè)節(jié)

39、點(diǎn)的size+1，新節(jié)點(diǎn)的size置為1；-附加成本：O(logn) 附加成本：O(logn)Phase 2：采用變色和旋轉(zhuǎn)方法，從葉子向上調(diào)整；-變色不改變size； 變色不改變size；-旋轉(zhuǎn)可能改變size：旋轉(zhuǎn)是局部操作 旋轉(zhuǎn)是局部操作，又，只有軸上的兩個(gè)節(jié)點(diǎn)的size可能違反定義只需要在旋轉(zhuǎn)操作后對違反節(jié)點(diǎn)size進(jìn)行修改 只需要在旋轉(zhuǎn)操作后，對違反節(jié)點(diǎn)size進(jìn)行修改-附加成本：旋轉(zhuǎn)為O(1)，總成本為O(logn)2）OS樹的維護(hù): 刪除算法Phase 1：物理上刪除y 在刪除y時(shí)從y上溯至根將 Phase 1：物理上刪除y，在刪除y時(shí)從y上溯至根，將所經(jīng)歷的節(jié)點(diǎn)的size均減1

40、；-附加成本：O(logn) 附加成本：O(logn)Phase 2：采用變色和旋轉(zhuǎn)方法，從葉子向上調(diào)整；-變色不改變size； 變色不改變size；-旋轉(zhuǎn)可能改變size，至多有3個(gè)旋轉(zhuǎn)；-附加成本：O(logn) -附加成本：O(logn)Remark：上面介紹的插入和刪除均是有效維護(hù)有效，有效維護(hù)保證擴(kuò)充前后的基本操作的漸近時(shí)間不變。11 遞歸與分治法(sch1)1.遞歸設(shè)計(jì)技術(shù)遞歸的定義：若一個(gè)對象部分地包含它自己或用它自己給自己定 若一個(gè)對象部分地包含它自己, 或用它自己給自己定義, 則稱這個(gè)對象是遞歸的；若一個(gè)過程直接地或間接地調(diào)用自己則稱這個(gè)過程是遞歸的過程。遞歸有兩種：直接遞歸

41、：自己調(diào)用自己；間接遞歸：A調(diào)用B，B調(diào)用A遞歸方法的三種應(yīng)用：以下三個(gè)方面常用到遞歸方法1、 遞歸定義：如自然數(shù)定義：1是自然數(shù)；-一個(gè)自然數(shù)加1(后繼)仍是自然數(shù)；注：“1是自然數(shù)”是遞歸的臨界條件2、遞歸的數(shù)據(jù)結(jié)構(gòu)：如，單鏈表節(jié)點(diǎn)是遞歸擴(kuò)展的3、問題的遞歸解法：如，漢諾塔問題的直觀解法2.遞歸程序的非遞歸化示例：n!的遞歸和非遞歸算法Fact1(n)/遞歸程序 Fact2(int n)/非遞歸程序 () 序 ()非序 if n=0 return 1; p=1;else return n*fact1(n-1); for i1 to n do pp*i; return p;Remark：(1

42、)遞歸算法易設(shè)計(jì)和分析，但執(zhí)行效率較低，常要轉(zhuǎn)化非遞歸程序；(2)遞歸算法的非遞歸實(shí)現(xiàn)通常有三種實(shí)現(xiàn)方法：利用棧消除遞歸 利用迭代法消除遞歸；末尾遞歸消除法3.算法設(shè)計(jì) (1)Fibonacci數(shù)； Fibonacci(n) /遞歸算法If n=0 or n =1 then Return n;Else Return Fibonacci(n-1) + Fibonacci(n-2)int fib(int n) / 非遞歸算法 int a = 1, b = 1; if(n=0 | n=1) return n; for(int i=2; i1：T(n)=n*T(n-1)+O(n) 得出T(n)=O(n

43、!)，該算法是最優(yōu)的(3)二分查找1) 基本思想：將有序序列（升序）等分為幾乎相等的兩部分，待查關(guān)鍵字與劃分元比較。如果小于劃分元，則遞歸處理左半部分，否則遞歸處理右半比較。非遞歸算法：Bi S h1(L ) /找到x返回下標(biāo)值，找不到返回-1 left1, rightn; flag0; /flag為標(biāo)志變量while (leftright and flag=0) do while (leftright and flag=0) do mid (left+right)/2;（此處有最小下界符號）if x=Lmid then flag1; if x=Lmid then flag1;else if

44、xLmid then rightmid-1;else leftmid+1;if flag=1 then return mid;else return -1; 2) 遞歸算法：BinarySearch2(L ,x,i, j) y(,j) /在有序表Li.j中查找xIf ij then return -1;If i=j thenif x=Li then return i;else return -1;else mid (i+j)/2;/（此處有最小下界符號）if x=Lmid then return mid;if x=Lmid then return mid;else if xLmid thenreturn BinarySearch2(L, x, i, mid-1);else return BinarySearch2(L, x, mid+1, j); 3) 遞歸算法時(shí)間分析N=1：T(n)=O(1)；n1：T(n)= T(n/2)+O(1) 得出T(n)=O(logn)(4)大整數(shù)乘法1) 普通遞歸乘法分析：X、Y是n位的二進(jìn)制數(shù)，設(shè)X是n/2位的A+ n/2位的B；Y是n/2位的C+ n/2位的D則X=A2n/2+B, Y=C2n/2+D 則XY=AC2n+(AD+BC) 2n/2+BD;其計(jì)算成本：T(n)=O(n2)2) 改進(jìn)