計算機(jī)算法設(shè)計與分析第2版2遞歸與分治策略-在線瀏覽
2024-12-03 14:35本頁面
【正文】 1時，問題比較簡單。 當(dāng) n＞ 1時，需要利用塔座 c作為輔助塔座。 由此可見， n個圓盤的移動問題可分為 2次 n1個圓盤的移動問題，這又可以遞歸地用上述方法來做。 遞歸的概念 例 6 Hanoi塔問題 void hanoi(int n, int a, int b, int c) { if (n 0) { hanoi(n1, a, c, b)。 hanoi(n1, c, b, a)。 缺點： 遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。 采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。 用遞推來實現(xiàn)遞歸函數(shù)。 后兩種方法在時空復(fù)雜度上均有較大改善，但其適用范圍有限。 因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。 這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然也可用分治法，但一般用 動態(tài)規(guī)劃 較好。 //解決小規(guī)模的問題 divide P into smaller subinstances P1,P2,...,Pk； //分解問題 for (i=1,i=k,i++) yi=divideandconquer(Pi)。 //將各子問題的解合并為原問題的解 } 分治法的基本步驟 人們從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。這種使子問題規(guī)模大致相等的做法是出自一種 平衡(balancing)子問題 的思想，它幾乎總是比子問題規(guī)模不等的做法要好。設(shè)分解閥值 n0=1，且 adhoc解規(guī)模為 1的問題耗費 1個單位時間。用 T(n)表示該分治法解規(guī)模為 |P|=n的問題所需的計算時間，則有： 11)()/()1()(???????nnnfmnkTOnT通過迭代法求得方程的解： ? ????1l o g0l o g )/()(nmjjjkm mnfknnT注意 ： 遞歸方程及其解只給出 n等于 m的方冪時 T(n)的值，但是如果認(rèn)為 T(n)足夠平滑，那么由 n等于 m的方冪時 T(n)的值可以估計 T(n)的增長速度。 分析： 如果 n=1即只有一個元素，則只要比較這個元素和 x就可以確定 x是否在表中。無論是在前面還是后面查找 x，其方法都和在 a中查找 x一樣，只不過是查找的規(guī)?？s小了。 分析： 很顯然此問題分解出的子問題相互獨立，即在 a[i]的前面或后面查找 x是獨立的子問題，因此滿足分治法的第四個適用條件。 分析： ? 該問題的規(guī)?？s小到一定的程度就可以容易地解決； ? 該問題可以分解為若干個規(guī)模較小的相同問題 。 二分搜索技術(shù) 給定已按升序排好序的 n個元素 a[0:n1]，現(xiàn)要在這 n個元素中找出一特定元素 x。 x, int l, int r) { while (r = l){ int m = (l+r)/2。 if (x a[m]) r = m1。 } return 1。因此，在最壞情況下， while循環(huán)被執(zhí)行了O(logn) 次。 大整數(shù)的乘法 請設(shè)計一個有效的算法，可以進(jìn)行兩個 n位大整數(shù)的乘法運算 ?小學(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) ?沒有改進(jìn) 11)()2/(4)1()(??????? nnnOnTOnT大整數(shù)的乘法 請設(shè)計一個有效的算法，可以進(jìn)行兩個 n位大整數(shù)的乘法運算 ?小學(xué)的方法： O(n2) ?效率太低 ?分治法 : XY = ac 2n + (ad+bc) 2n/2 + bd 為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。 大整數(shù)的乘法 請設(shè)計一個有效的算法，可以進(jìn)行兩個 n位大整數(shù)的乘法運算 ?小學(xué)的方法： O(n2) ?效率太低 ?分治法 : O() ?較大的改進(jìn) ?更快的方法 ?? ?如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。該方法也可以看作是一個復(fù)雜的分治算法。因此，算出矩陣 C的 個元素所需的計算時間為 O(n3) ?傳統(tǒng)方法 ： O(n3) Strassen矩陣乘法 使用與上例類似的技術(shù)，將矩陣 A， B和 C中每一矩陣都分塊成 4個大小相等的子矩陣。 ???????????????????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)，計算 2個２ ２矩陣的乘積， 7次乘法是必要的?；蛟S應(yīng)當(dāng)研究３ ３或５ ５矩陣的更好算法。目前最好的計算時間上界是 O() ?是否能找到 O(n2)的算法？ 棋盤覆蓋 在一個 2k 2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。 棋盤覆蓋 當(dāng) k0時，將 2k 2k棋盤分割為 4個 2k1 2k1 子棋盤 (a)所示。為了將這 3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個 L型骨牌覆蓋這 3個較小棋盤的會合處，如 (b)所示，從而將原問題轉(zhuǎn)化為 4個較小規(guī)模的棋盤覆蓋問題。 棋盤覆蓋 void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return。 // 分割棋盤 // 覆蓋左上角子棋盤 if (dr tr + s amp。 dc tc + s) // 特殊方格在此棋盤中 chessBoard(tr, tc, dr, dc, s)。 // 覆蓋其余方格 chessBoard(tr, tc, tr+s1, tc+s1, s)。amp。 else {// 此棋盤中無特殊方格 // 用 t 號 L型骨牌覆蓋左下角 board[tr + s 1][tc + s] = t。} // 覆蓋左下角子棋盤 if (dr = tr + s amp。 dc tc + s) // 特殊方格在此
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1