【文章內容簡介】 49 二分搜索技術 ?給定已按升序 排好序 的 n個元素 a[0:n1]，現要在這 n個元素中找出一特定元素 x。 ?也稱為折半查找法 ,它充分利用了元素間的次序關系，采用分治策略，可在最壞的情況下用 O(log n)完成搜索任務。 2021年 11月 12日 50 分析： 如果 n=1即只有一個元素，則只要比較這個元素和 x就可以確定 x是否在表中。因此這個問題滿足分治法的第一個適用條件 分析： 比較 x和 a的中間元素 a[mid]，若 x=a[mid]，則 x在 L中的位置就是 mid；如果 xa[mid]，由于 a是遞增排序的，因此假如 x在 a中的話， x必然排在 a[mid]的前面，所以我們只要在a[mid]的前面查找 x即可；如果 xa[i]，同理我們只要在 a[mid]的后面查找 x即可。無論是在前面還是后面查找 x，其方法都和在 a中查找 x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。 分析： 很顯然此問題分解出的子問題相互獨立，即在 a[i]的前面或后面查找 x是獨立的子問題，因此滿足分治法的第四個適用條件。 給定已按升序 排好序 的 n個元素 a[0:n1]，現要在這 n個元素中找出一特定元素 x。 分析： ? 該問題的規(guī)?？s小到一定的程度就可以容易地解決； ? 該問題可以分解為若干個規(guī)模較小的相同問題 。 ? 分解出的子問題的解可以合并為原問題的解； ? 分解出的各個子問題是相互獨立的。 二分搜索技術 2021年 11月 12日 51 ?基本思想是，將 n個元素分成個數大致相同的兩半，取 a[n/2]與欲查找的 x作比較，如果 x=a[n/2]則找到 x，算法終止。如果xa[n/2]，則我們只要在數組 a的左半部繼續(xù)搜索 x（這里假設數組元素呈升序排列）。如果 xa[n/2]，則我們只要在數組 a的右半部繼續(xù)搜索 x。 2021年 11月 12日 52 ?二分搜索法的應用極其廣泛，而且它的思想易于理解，但是要寫一個正確的二分搜索算法也不是一件簡單的事。第一個二分搜索算法早在 1946年就出現了，但是第一個完全正確的二分搜索算法直到 1962年才出現。 Bentley在他的著作 《 Writing Correct Programs》 中寫道， 90%的計算機專家不能在 2小時內寫出完全正確的二分搜索算法。 2021年 11月 12日 53 二分搜索技術 ?二分搜索算法： templateclass Type int BinarySearch(Type a[], const Typeamp。 x, int n) { int left=0。 int right=n1。 while (left=right){ int middle = (left+right)/2。 if (x == a[middle]) return middle。 if (x a[middle]) left = middle+1。 else right = middle1。 } return 1。 } 算法復雜度分析： 每執(zhí)行一次算法的 while循環(huán)， 待搜索數組的大小減少一半。因此，在最壞情況下， while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內運算需要 O(1) 時間，因此整個算法在最壞情況下的計算時間復雜性為 O(logn) 。 2021年 11月 12日 54 2021年 11月 12日 55 2021年 11月 12日 56 2021年 11月 12日 57 2021年 11月 12日 58 2021年 11月 12日 59 2021年 11月 12日 60 2021年 11月 12日 61 大整數的乘法 ? 通常，在分析一個算法的計算復雜性時，都將加法和乘法運算當作是基本運算來處理，即將執(zhí)行一次加法或乘法運算所需的計算時間當作一個僅取決于計算機硬件處理速度的常數。 這個假定僅在計算機硬件能對參加運算的整數直接表示和處理時才是合理的。然而，在某些情況下，我們要處理很大的整數，它無法在計算機硬件能直接表示的范圍內進行處理。若用浮點數來表示它，則只能近似地表示它的大小，計算結果中的有效數字也受到限制。若要精確地表示大整數并在計算結果中要求精確地得到所有位數上的數字，就必須用軟件的方法來實現大整數的算術運算。 2021年 11月 12日 62 大整數的乘法 請設計一個有效的算法，可以進行兩個 n位大整數的乘法運算 ?小學的方法： 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 復雜度分析 T(n)=O(n2) ?沒有改進 11)()2/(4)1()(??????? nnnOnTOnT2021年 11月 12日 63 ?如果按上式計算 X*Y，則我們必須進行 4次 n/2位整數的乘法 (AC， AD， BC和 BD)，以及 3次不超過 n位的整數加法，此外還要做 2次移位 (分別對應于式 (1)中乘 2n和乘 2n/2)。所有這些加法和移位共用O(n)步運算。設 T(n)是 2個 n位整數相乘所需的運算總數，由此遞歸式迭代過程如下： T(n)=4T(n/2)+ =4(4T(n/4)+/2)+ =16(T(n/8)+ /4)+3/2+ =…… = +4k1 *2c+4k2 *4c+……+4c2k 1+c2k =O（ 4k） = O(nlog4) =O（ n2） 2021年 11月 12日 64 大整數的乘法 請設計一個有效的算法，可以進行兩個 n位大整數的乘法運算 ?小學的方法： O(n2) ?效率太低 ?分治法 : XY = ac 2n + (ad+bc) 2n/2 + bd 為了降低時間復雜度，必須減少乘法的次數。 1. XY = ac 2n + ((ab)(dc)+ac+bd) 2n/2 + bd 2. XY = ac 2n + ((a+b)(c+d)acbd) 2n/2 + bd 復雜度分析 T(n)=O(nlog3) =O()?較大的改進 11)()2/(3)1()(??????? nnnOnTOnT細節(jié)問題 ：兩個 XY的復雜度都是 O(nlog3)，但考慮到 a+c,b+d可能得到 m+1位的結果，使問題的規(guī)模變大，故不選擇第 2種方案。 2021年 11月 12日 65 ?用解遞歸方程的迭代公式法，不妨設 n=2^k： T(n)=3T(n/2)+ =3(3T(n/4)+/2)+ =9(T(n/8)+ /4)+3/2+ =…… =3^k +3^(k1) *2c+3^(k2) *4c+……+3c2^(k 1)+c2^k = O(n^log3) 則得到 T(n)=O(n^log3)=O(n^)。 2021年 11月 12日 66 大整數的乘法 請設計一個有效的算法，可以進行兩個 n位大整數的乘法運算 ?小學的方法： O(n2) ?效率太低 ?分治法 : O() ?較大的改進 ?更快的方法 ?? ?如果將大整數分成更多段，用更復雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。 ?最終的，這個思想導致了 快速傅利葉變換 (Fast Fourier Transform)的產生。該方法也可以看作是一個復雜的分治算法。 2021年 11月 12日 67 A和 B的乘積矩陣 C中的元素 C[i,j]定義為 : ??? nkjkBkiAjiC1]][[]][[]][[若依此定義來計算 A和 B的乘積矩陣 C，則每計算 C的一個元素 C[i][j]，需要做 n次乘法和 n1次加法。因此，算出矩陣 C的 個元素所需的計算時間為 O(n3) Strassen矩陣乘法 2n2021年 11月 12日 68 將矩陣 A， B和 C中每一矩陣都分塊成 4個大小相等的子矩陣。由此可將方程 C=AB重寫為： ?傳統(tǒng)方法 ： O(n3) ?分治法 : ???????????????????222112112221121122211211BBBBAAAACCCC由此可得： 2112111111 BABAC ??2212121112 BABAC ??2122112121 BABAC ??2222122122 BABAC ??復雜度分析 T(n)=O(n3) 22)()2/(8)1()(2 ??????? nnnOnTOnT Strassen矩陣乘法 2021年 11月 12日 69 ?傳統(tǒng)方法 ： O(n3) ?分治法 : 為了降低時間復雜度，必須減少乘法的次數。（ strassen方法） ???????????????????222112112221121122211211BBBBAAAACCCC)( 2212111 BBAM ??2212112 )( BAAM ??1122213 )( BAAM ??)( 1121224 BBAM ??))(( 221122115 BBAAM ???))(( 222122126 BBAAM ???))(( 121121117 BBAAM ???624511 MMMMC ????2112 MMC ??4321 MMC ??731522 MMMMC ????復雜度分析 T(n)=O(nlog7) =O()?較大的改進 22)()2/(7)1()(2 ??????? nnnOnTOnT Strassen矩陣乘法 2021年 11月 12日 70 ?更快的方法 ?? ?Hopcroft和 Kerr已經證明 (1971)，計算 2個２ ２矩陣的乘積， 7次乘法是必要的。因此，要想進一步改進矩陣乘法的時間復雜性，就不能再基于計算2 2矩陣的 7次乘法這樣的方法了?；蛟S應當研究３ ３或５ ５矩陣的更好算法。 ?在 Strassen之后又有許多算法改進了矩陣乘法的計算時間復雜性。目前最好的計算時間上界是 O() ?是否能找到 O(n2)的算法？ Strassen矩陣乘法 2021年 11月 12日 71 ?n的問題 ?? ?以上分析中假設 A,B,C都是 n n矩陣，并假定 n是 2的冪。 ?如果 n