【正文】 97] [13 76] [27] 第一步 第二步 [38 49 65 97] [13 27 76] 第三步 [13 27 38 49 65 76 97] 合并排序 ?最壞時(shí)間復(fù)雜度： O(nlogn) ?平均時(shí)間復(fù)雜度： O(nlogn) ?輔助空間： O(n) 快速排序 在快速排序中，記錄的比較和交換是從兩端向中間 進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單 元，關(guān)鍵字較小的記錄一次就能交換到前面單元， 記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次 數(shù)較少。 //對(duì)右半段排序 } } 快速排序 templateclass Type int Partition (Type a[], int p, int r) { int i = p, j = r + 1。 if (i = j) break。 return j。 ji{5, 2, 5, 6, 7, 8} i++。 } 快速排序 快速排序算法的性能取決于劃分的對(duì)稱性。 int i=RandomizedPartition(a,p,r), j=ip+1。 線性時(shí)間選擇 如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分出的 2個(gè)子數(shù)組的長(zhǎng)度都至少為原數(shù)組長(zhǎng)度的 ε倍 (0ε1是某個(gè)正常數(shù) )，那么就可以 在最壞情況下 用 O(n)時(shí)間完成選擇任務(wù)。 ?將 n個(gè)輸入元素劃分成 ?n/5?個(gè)組，每組 5個(gè)元素，只可能有一個(gè)組不是 5個(gè)元素。以這個(gè)元素作為劃分基準(zhǔn)。而當(dāng)n≥75時(shí)， 3(n5)/10≥n/4所以按此基準(zhǔn)劃分所得的 2個(gè)子數(shù)組的長(zhǎng)度都至少縮短 1/4。 for ( int i = 0。 int i=Partition(a,p,r, x), j=ip+1。這 2點(diǎn)保證了 T(n)的遞歸式中 2個(gè)自變量之和n/5+3n/4=19n/20=εn， 0ε1。 ?為了使問(wèn)題易于理解和分析，先來(lái)考慮 一維 的情形。 ?遞歸地在 S1和 S2上找出其最接近點(diǎn)對(duì) {p1,p2}和 {q1,q2}，并設(shè) d=min{|p1p2|,|q1q2|}， S中的最接近點(diǎn)對(duì)或者是 {p1,p2}，或者是 {q1,q2}，或者是某個(gè) {p3,q3}，其中 p3∈ S1且 q3∈ S2。 ?因此，我們用線性時(shí)間就能找到區(qū)間 (md,m]和 (m,m+d]中所有點(diǎn)，即 p3和 q3。其中 m為 S中各點(diǎn) x坐標(biāo)的中位數(shù)。 滿足這個(gè)條件的 P2中的點(diǎn)一定落在一個(gè) d 2d的矩形 R中 ?由 d的意義可知， P2中任何 2個(gè) S中的點(diǎn)的距離都不小于 d。設(shè) u， v是位于同一小矩形中的 2個(gè)點(diǎn)，則 distance(u,v)d。由上面的分析可知，這種投影點(diǎn)最多只有 6個(gè)。 if (n 2) return 。 dm=min(d1,d2)。 按分治策略，將所有的選手分為兩半， n個(gè)選手的比賽日程表就可以通過(guò)為 n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。 。這時(shí)只要讓這 2個(gè)選手進(jìn)行比賽就可以了。 return d。 構(gòu)造 S1和 S2； //S1={p∈ S|x(p)=m}, S2={p∈ S|x(p)m} d1=cpair2(S1)。對(duì) P1中每一點(diǎn)最多只要檢查 P2中排好序的相繼 6個(gè)點(diǎn)。 22222 3625)3/2()2/())()(())()(( dddvyuyvxux ???????為了 確切地知道要檢查哪 6個(gè)點(diǎn) ，可以將 p和P2中所有 S2的點(diǎn)投影到垂直線 l上。 ?因此，在分治法的合并步驟中 最多只需要檢查 6 n/2=3n個(gè)候選者 能否在線性時(shí)間內(nèi)找到 p3,q3？ 證明 :將矩形 R的長(zhǎng)為 2d的邊 3等分，將它的長(zhǎng)為d的邊 2等分，由此導(dǎo)出 6個(gè) (d/2) (2d/3)的矩形。 ?遞歸地在 S1和 S2上找出其最小距離 d1和 d2，并設(shè)d=min{d1,d2}， S中的最接近點(diǎn)對(duì)或者是 d，或者是某個(gè) {p,q}，其中 p∈ P1且 q∈ P2。 能否在線性時(shí)間內(nèi)找到 p3,q3？ 最接近點(diǎn)對(duì)問(wèn)題 ?下面來(lái)考慮二維的情形。 ?由于在 S1中，每個(gè)長(zhǎng)度為 d的半閉區(qū)間至多包含一個(gè)點(diǎn)（否則必有兩點(diǎn)距離小于 d），并且 m是 S1和 S2的分割點(diǎn)，因此(md,m]中至多包含 S中的一個(gè)點(diǎn)。最接近點(diǎn)對(duì)即為這 n個(gè)實(shí)數(shù)中相差最小的 2個(gè)實(shí)數(shù)。當(dāng)然，除了 5和 75之外，還有其他選擇。 else return Select(a,i+1,r,kj)。 i++ ) 將 a[p+5*i]至 a[p+5*i+4]的第 3小元素 與 a[p+i]交換位置 。 return a[p+k1]。在這種情況下，找出的基準(zhǔn) x至少比 3(n5)/10個(gè)元素大，因?yàn)樵诿恳唤M中有 2個(gè)元素小于本組的中位數(shù)，而 n/5個(gè)中位數(shù)中又有 (n5)/10個(gè)小于基準(zhǔn) x。 ?遞歸調(diào)用 select來(lái)找出這 ?n/5?個(gè)元素的中位數(shù)。所以，在最壞情況下，算法所需的計(jì)算時(shí)間 T(n)滿足遞歸式T(n)≤T(9n/10)+O(n) 。 else return RandomizedSelect(a,i+1,r,kj)。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被劃分時(shí)，可以在 a[p:r]中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱的。 Swap(a[i], a[p])。 ji{5, 7, 5, 2, 6, 8} i++。 } a[p] = a[j]。 // 將 x的元素交換到左邊區(qū)域 // 將 x的元素交換到右邊區(qū)域 while (true) { while (a[++i] x)。 QuickSort (a,p,q1)。 //合并到數(shù)組 b copy(a, b, left, right)。 void MergeSort(Type a[], int left, int right) { if (leftright) {//至少有 2個(gè)元素 int i=(left+right)/2。 dc = tc + s) // 特殊方格在此棋盤中 chessBoard(tr+s, tc+s, dr, dc, s)。 else {// 用 t 號(hào) L型骨牌覆蓋右上角 board[tr + s][tc + s 1] = t。 // 覆蓋其余方格 chessBoard(tr, tc+s, tr+s1, tc+s, s)。} // 覆蓋右上角子棋盤 if (dr tr + s amp。amp。遞歸地使用這種分割，直至棋盤簡(jiǎn)化為棋盤 1 1。在棋盤覆蓋問(wèn)題中，要用圖示的 4種不同形態(tài)的 L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何 2個(gè) L型骨牌不得重疊覆蓋。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算 2 2矩陣的 7次乘法這樣的方法了。 Strassen矩陣乘法 A和 B的乘積矩陣 C中的元素 C[i,j]定義為 : ??? nkjkBkiAjiC1]][[]][[]][[若依此定義來(lái)計(jì)算 A和 B的乘積矩陣 C，則每計(jì)算 C的一個(gè)元素 C[i][j]，需要做 n次乘法和 n1次加法。 1. XY = ac 2n + ((ac)(bd)+ac+bd) 2n/2 + bd 2. XY = ac 2n + ((a+c)(b+d)acbd) 2n/2 + bd 復(fù)雜度分析 T(n)=O(nlog3) =O()?較大的改進(jìn) 11)()2/(3)1()(??????? nnnOnTOnT細(xì)節(jié)