【文章內(nèi)容簡介】 // 找到 x時返回其在數(shù)組中的位置，否則返回 1 int left = 0。 int right = n 1。 while (left = right) { int middle = (left + right)/2。 if (x == a[middle]) return middle。 if (x a[middle]) left = middle + 1。 else right = middle 1。 } return 1。 // 未找到 x } 算法復(fù)雜度分析： 每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運算需要 O(1) 時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為 O(logn) 。 思考題： 給定 a，用二分法設(shè)計出求 an的算法。 大整數(shù)的乘法 請設(shè)計一個有效的算法，可以進(jìn)行兩個 n位大整數(shù)的乘法運算 ?小學(xué)的方法： O(n2) ?效率太低 ?分治法 : a b c d 復(fù)雜度分析 T(n)=O(n2) ?沒有改進(jìn) ? 11)()2/(4)1()(??????? nnnOnTOnTX = Y = X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd 大整數(shù)的乘法 請設(shè)計一個有效的算法，可以進(jìn)行兩個 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()?較大的改進(jìn) ? 11)()2/(3)1()(??????? nnnOnTOnT細(xì)節(jié)問題 ：兩個 XY的復(fù)雜度都是 O(nlog3)，但考慮到 a+c,b+d可能得到 m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第 2種方案。 大整數(shù)的乘法 請設(shè)計一個有效的算法，可以進(jìn)行兩個 n位大整數(shù)的乘法運算 ?小學(xué)的方法： O(n2) ?效率太低 ?分治法 : O() ?較大的改進(jìn) ?更快的方法 ?? ?如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。 ?最終的，這個思想導(dǎo)致了 快速傅利葉變換 (Fast Fourier Transform)的產(chǎn)生。該方法也可以看作是一個復(fù)雜的分治算法，對于大整數(shù)乘法，它能在 O(nlogn)時間內(nèi)解決。 ?是否能找到線性時間的算法？？？目前為止還沒有結(jié)果。 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) ?沒有改進(jìn) ? 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()?較大的改進(jìn) ? 22)()2/(8)1()(2 ??????? nnnOnTOnTStrassen矩陣乘法 ?傳統(tǒng)方法 ： O(n3) ?分治法 : O() ?更快的方法 ?? ?Hopcroft和 Kerr已經(jīng)證明 (1971)，計算 2個２ ２矩陣的乘積， 7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時間復(fù)雜性，就不能再基于計算 2 2矩陣的 7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究３ ３或５ ５矩陣的更好算法。 ?在 Strassen之后又有許多算法改進(jìn)了矩陣乘法的計算時間復(fù)雜性。目前最好的計算時間上界是 O() ?是否能找到 O(n2)的算法？？？目前為止還沒有結(jié)果。 棋盤覆蓋 在一個 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。 棋盤覆蓋 public 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)。} // 覆蓋右上角子棋盤 if (dr tr + s amp。amp。 dc = tc + s) // 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s)。 else {// 此棋盤中無特殊方格 // 用 t 號 L型骨牌覆蓋左下角 board[tr + s 1][tc + s] = t。 // 覆蓋其余方格 chessBoard(tr, t