計算機算法設(shè)計與分析第2版2遞歸與分治策略(編輯修改稿)
2024-11-12 14:35 本頁面
【文章內(nèi)容簡介】 條件。 二分搜索技術(shù) 給定已按升序排好序的 n個元素 a[0:n1]，現(xiàn)要在這 n個元素中找出一特定元素 x。 分析： ? 該問題的規(guī)?？s小到一定的程度就可以容易地解決； ? 該問題可以分解為若干個規(guī)模較小的相同問題 。 ? 分解出的子問題的解可以合并為原問題的解； ? 分解出的各個子問題是相互獨立的。 二分搜索技術(shù) 給定已按升序排好序的 n個元素 a[0:n1]，現(xiàn)要在這 n個元素中找出一特定元素 x。 據(jù)此容易設(shè)計出 二分搜索算法 ： templateclass Type int BinarySearch(Type a[], const Typeamp。 x, int l, int r) { while (r = l){ int m = (l+r)/2。 if (x == a[m]) return m。 if (x a[m]) r = m1。 else l = m+1。 } return 1。 } 算法復(fù)雜度分析： 每執(zhí)行一次算法的 while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下， while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運算需要 O(1) 時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為 O(logn) 。 大整數(shù)的乘法 請設(shè)計一個有效的算法，可以進行兩個 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) ?沒有改進 11)()2/(4)1()(??????? nnnOnTOnT大整數(shù)的乘法 請設(shè)計一個有效的算法，可以進行兩個 n位大整數(shù)的乘法運算 ?小學(xué)的方法： O(n2) ?效率太低 ?分治法 : XY = ac 2n + (ad+bc) 2n/2 + bd 為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。 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()?較大的改進 11)()2/(3)1()(??????? nnnOnTOnT細節(jié)問題 ：兩個 XY的復(fù)雜度都是 O(nlog3)，但考慮到 a+c,b+d可能得到 m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第 2種方案。 大整數(shù)的乘法 請設(shè)計一個有效的算法，可以進行兩個 n位大整數(shù)的乘法運算 ?小學(xué)的方法： O(n2) ?效率太低 ?分治法 : O() ?較大的改進 ?更快的方法 ?? ?如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。 ?最終的，這個思想導(dǎo)致了 快速傅利葉變換 (Fast Fourier Transform)的產(chǎn)生。該方法也可以看作是一個復(fù)雜的分治算法。 Strassen矩陣乘法 A和 B的乘積矩陣 C中的元素 C[i,j]定義為 : ??? nkjkBkiAjiC1]][[]][[]][[若依此定義來計算 A和 B的乘積矩陣 C，則每計算 C的一個元素 C[i][j]，需要做 n次乘法和 n1次加法。因此，算出矩陣 C的 個元素所需的計算時間為 O(n3) ?傳統(tǒng)方法 ： O(n3) Strassen矩陣乘法 使用與上例類似的技術(shù)，將矩陣 A， B和 C中每一矩陣都分塊成 4個大小相等的子矩陣。由此可將方程 C=AB重寫為： ?傳統(tǒng)方法 ： O(n3) ?分治法 : ???????????????????222112112221121122211211BBBBAAAACCCC由此可得： 2112111111 BABAC ??2212121112 BABAC ??2122112121 BABAC ??2222122122 BABAC ??復(fù)雜度分析 T(n)=O(n3) 22)()2/(7)1()(2 ??????? nnnOnTOnTStrassen矩陣乘法 ?傳統(tǒng)方法 ： O(n3) ?分治法 : 為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。 ???????????????????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()?較大的改進 22)()2/(8)1()(2 ??????? nnnOnTOnTStrassen矩陣乘法 ?傳統(tǒng)方法 ： O(n3) ?分治法 : O() ?更快的方法 ?? ?Hopcroft和 Kerr已經(jīng)證明 (1971)，計算 2個２ ２矩陣的乘積， 7次乘法是必要的。因此，要想進一步改進矩陣乘法的時間復(fù)雜性，就不能再基于計算 2 2矩陣的 7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究３ ３或５ ５矩陣的更好算法。 ?在 Strassen之后又有許多算法改進了矩陣乘法的計算時間復(fù)雜性。目前最好的計算時間上界是 O() ?是否能找到 O(n2)的算法？ 棋盤覆蓋 在一個 2k 2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的 4種不同形態(tài)的 L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何 2個 L型骨牌不得重疊覆蓋。 棋盤覆蓋 當(dāng) k0時，將 2k 2k棋盤分割為 4個 2k1 2k1 子棋盤 (a)所示。 特殊方格必位于 4個較小子棋盤之一中，其余 3個子棋盤中無特殊方格。為了將這 3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個 L型骨牌覆蓋這 3個較小棋盤的會合處，如 (b)所示，從而將原問題轉(zhuǎn)化為 4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤 1 1。 棋盤覆蓋 void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return。 int t = tile++, // L型骨牌號 s = size/2。 // 分割棋盤 // 覆蓋左上角子棋盤 if (dr tr + s amp。amp。 dc tc + s) // 特殊方格在此棋盤中 chessBoard(tr, tc, dr, dc, s)。 else {// 此棋盤中無特殊方格 // 用 t 號 L型骨牌覆蓋右下角 board[tr + s 1][tc + s 1] = t。 // 覆蓋其余方格 chessBoard(tr, tc, tr+s1, tc+s1, s)。}
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1