計(jì)算機(jī)算法設(shè)計(jì)與分析（第2版）2遞歸與分治策略-預(yù)覽頁(yè)
【正文】 for (i=1,i=k,i++) yi=divideandconquer(Pi)。這種使子問(wèn)題規(guī)模大致相等的做法是出自一種 平衡(balancing)子問(wèn)題 的思想，它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。用 T(n)表示該分治法解規(guī)模為 |P|=n的問(wèn)題所需的計(jì)算時(shí)間，則有： 11)()/()1()(???????nnnfmnkTOnT通過(guò)迭代法求得方程的解： ? ????1l o g0l o g )/()(nmjjjkm mnfknnT注意 ： 遞歸方程及其解只給出 n等于 m的方冪時(shí) T(n)的值，但是如果認(rèn)為 T(n)足夠平滑，那么由 n等于 m的方冪時(shí) T(n)的值可以估計(jì) T(n)的增長(zhǎng)速度。無(wú)論是在前面還是后面查找 x，其方法都和在 a中查找 x一樣，只不過(guò)是查找的規(guī)?？s小了。 分析： ? 該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決； ? 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題 。 x, int l, int r) { while (r = l){ int m = (l+r)/2。 } return 1。 大整數(shù)的乘法 請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè) n位大整數(shù)的乘法運(yùn)算 ?小學(xué)的方法： O(n2) ?效率太低 ?分治法 : X = Y = X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd a b c d 復(fù)雜度分析 T(n)=O(n2) ?沒(méi)有改進(jìn) 11)()2/(4)1()(??????? nnnOnTOnT大整數(shù)的乘法 請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè) n位大整數(shù)的乘法運(yùn)算 ?小學(xué)的方法： O(n2) ?效率太低 ?分治法 : XY = ac 2n + (ad+bc) 2n/2 + bd 為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。該方法也可以看作是一個(gè)復(fù)雜的分治算法。 ???????????????????222112112221121122211211BBBBAAAACCCC)( 2212111 BBAM ??2212112 )( BAAM ??1122213 )( BAAM ??)( 1121224 BBAM ??))(( 221122115 BBAAM ???))(( 222122126 BBAAM ???))(( 121121117 BBAAM ???624511 MMMMC ????2112 MMC ??4321 MMC ??731522 MMMMC ????復(fù)雜度分析 T(n)=O(nlog7) =O()?較大的改進(jìn) 22)()2/(8)1()(2 ??????? nnnOnTOnTStrassen矩陣乘法 ?傳統(tǒng)方法 ： O(n3) ?分治法 : O() ?更快的方法 ?? ?Hopcroft和 Kerr已經(jīng)證明 (1971)，計(jì)算 2個(gè)２ ２矩陣的乘積， 7次乘法是必要的。目前最好的計(jì)算時(shí)間上界是 O() ?是否能找到 O(n2)的算法？ 棋盤(pán)覆蓋 在一個(gè) 2k 2k 個(gè)方格組成的棋盤(pán)中，恰有一個(gè)方格與其它方格不同，稱(chēng)該方格為一特殊方格，且稱(chēng)該棋盤(pán)為一特殊棋盤(pán)。為了將這 3個(gè)無(wú)特殊方格的子棋盤(pán)轉(zhuǎn)化為特殊棋盤(pán)，可以用一個(gè) L型骨牌覆蓋這 3個(gè)較小棋盤(pán)的會(huì)合處，如 (b)所示，從而將原問(wèn)題轉(zhuǎn)化為 4個(gè)較小規(guī)模的棋盤(pán)覆蓋問(wèn)題。 // 分割棋盤(pán) // 覆蓋左上角子棋盤(pán) if (dr tr + s amp。 // 覆蓋其余方格 chessBoard(tr, tc, tr+s1, tc+s1, s)。 else {// 此棋盤(pán)中無(wú)特殊方格 // 用 t 號(hào) L型骨牌覆蓋左下角 board[tr + s 1][tc + s] = t。 dc tc + s) // 特殊方格在此棋盤(pán)中 chessBoard(tr+s, tc, dr, dc, s)。amp。} } 復(fù)雜度分析 T(n)=O(4k) 漸進(jìn)意義下的最優(yōu)算法 ???????? 00)1()1(4)1()(kkOkTOkT合并排序 基本思想： 將待排序元素分成大小大致相同的 2個(gè)子集合，分別對(duì) 2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。 merge(a, b, left, i, right)。 templateclass Type void QuickSort (Type a[], int p, int r) { if (pr) { int q=Partition(a,p,r)。 Type x=a[p]。 Swap(a[i], a[j])。 } 初始序列 {6, 7, 5, 2, 5, 8} j。 ji完成 {6, 7, 5, 2, 5, 8} {5, 2, 5} 6 {7, 8} templateclass Type int RandomizedPartition (Type a[], int p, int r) { int i = Random(p,r)。通過(guò)修改算法 partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。 if (k=j) return RandomizedSelect(a,p,i,k)。 例如，若 ε=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長(zhǎng)度至少縮短 1/10。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共 ?n/5?個(gè)。 線性時(shí)間選擇 設(shè)所有元素互不相同。 Type Select(Type a[], int p, int r, int k) { if (rp75) { 用某個(gè)簡(jiǎn)單排序算法對(duì)數(shù)組 a[p:r]排序 。 i=(rp4)/5。 if (k=j) return Select(a,p,i,k)。這是使 T(n)=O(n)的關(guān)鍵之處。此時(shí)，S中的 n個(gè)點(diǎn)退化為 x軸上的 n個(gè)實(shí)數(shù) x1,x2,…,xn 。 ?能否在線性時(shí)間內(nèi)找到 p3,q3？ 最接近點(diǎn)對(duì)問(wèn)題 ?如果 S的最接近點(diǎn)對(duì)是 {p3,q3}，即 |p3q3|d，則 p3和 q3兩者與 m的距離不超過(guò) d， 即 p3∈ (md,m]， q3∈ (m,m+d]。 從而我們用線性時(shí)間就可以將 S1的解和 S2的解合并成為 S的解 。由此將 S分割為 S1和 S2。由此可以推出 矩形 R中最多只有 6個(gè) S中的點(diǎn) 。這與 d的意義相矛盾。 ?因此，若將 P1和 P2中所有 S中點(diǎn)按其 y坐標(biāo)排好序，則對(duì) P1中所有點(diǎn)，對(duì)排好序的點(diǎn)列作一次掃描，就可以找出所有最接近點(diǎn)對(duì)的候選者。 m=S中各點(diǎn) x間坐標(biāo)的中位數(shù) 。 設(shè) P1是 S1中距垂直分割線 l的距離在 dm之內(nèi)的所有點(diǎn)組成的集合； P2是 S2中距分割線 l的距離在 dm之內(nèi)所有點(diǎn)組成的集合； 將 P1和 P2中點(diǎn)依其 y坐標(biāo)值排序； 并設(shè) X和 Y是相應(yīng)的已排好序的點(diǎn)列； 通過(guò)掃描 X以及對(duì)于 X中每個(gè)點(diǎn)檢查 Y中與其距離在 dm之內(nèi)的所有點(diǎn) (最多 6個(gè) )可以完成合并； 當(dāng) X中的掃描指針逐次向上移動(dòng)時(shí)， Y中的掃描指針可在寬為 2dm的區(qū)間內(nèi)移動(dòng)； 設(shè) dl是按這種掃描方式找到的點(diǎn)對(duì)間的最小距離； d=min(dm,dl)。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下 2個(gè)選手時(shí)，比賽日程表的制定就變得很
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1