【正文】 位于 4個較小子棋盤之一中，其余 3個子棋盤中無特殊方格。在棋盤覆蓋問題中，要用圖示的 4種不同形態(tài)的 L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何 2個 L型骨牌不得重疊覆蓋。 ?在 Strassen之后又有許多算法改進了矩陣乘法的計算時間復雜性。因此，要想進一步改進矩陣乘法的時間復雜性，就不能再基于計算 2 2矩陣的 7次乘法這樣的方法了。由此可將方程 C=AB重寫為： ?傳統(tǒng)方法 ： O(n3) ?分治法 : ???????????????????222112112221121122211211BBBBAAAACCCC由此可得： 2112111111 BABAC ??2212121112 BABAC ??2122112121 BABAC ??2222122122 BABAC ??復雜度分析 T(n)=O(n3) 22)()2/(7)1()(2 ??????? nnnOnTOnTStrassen矩陣乘法 ?傳統(tǒng)方法 ： O(n3) ?分治法 : 為了降低時間復雜度，必須減少乘法的次數(shù)。 Strassen矩陣乘法 A和 B的乘積矩陣 C中的元素 C[i,j]定義為 : ??? nkjkBkiAjiC1]][[]][[]][[若依此定義來計算 A和 B的乘積矩陣 C，則每計算 C的一個元素 C[i][j]，需要做 n次乘法和 n1次加法。 ?最終的，這個思想導致了 快速傅利葉變換 (Fast Fourier Transform)的產生。 1. XY = ac 2n + ((ac)(bd)+ac+bd) 2n/2 + bd 2. XY = ac 2n + ((a+c)(b+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種方案。循環(huán)體內運算需要 O(1) 時間，因此整個算法在最壞情況下的計算時間復雜性為 O(logn) 。 } 算法復雜度分析： 每執(zhí)行一次算法的 while循環(huán)， 待搜索數(shù)組的大小減少一半。 else l = m+1。 if (x == a[m]) return m。 據(jù)此容易設計出 二分搜索算法 ： templateclass Type int BinarySearch(Type a[], const Typeamp。 ? 分解出的子問題的解可以合并為原問題的解； ? 分解出的各個子問題是相互獨立的。 二分搜索技術 給定已按升序排好序的 n個元素 a[0:n1]，現(xiàn)要在這 n個元素中找出一特定元素 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即可。通常假定 T(n)是單調上升的，從而當 mi≤nmi+1時， T(mi)≤T(n)T(mi+1)。再設將原問題分解為 k個子問題以及用 merge將 k個子問題的解合并為原問題的解需用 f(n)個單位時間。 分治法的復雜性分析 一個分治法將規(guī)模為 n的問題分成 k個規(guī)模為 n／ m的子問題去解。即將一個問題分成大小相等的 k個子問題的處理方法是行之有效的。 //遞歸的解各子問題 return merge(y1,...,yk)。 divideandconquer(P) { if ( | P | = n0) adhoc(P)。 這條特征是應用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應用 能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮 貪心算法 或 動態(tài)規(guī)劃 。 遞歸小結 分治法的適用條件 分治法所能解決的問題一般具有以下幾個特征： ? 該問題的規(guī)模縮小到一定的程度就可以容易地解決； ? 該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有 最優(yōu)子結構性質 ? 利用該問題分解出的子問題的解可以合并為該問題的解； ? 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 通過 變換能 將一些遞歸轉化為尾遞歸，從而迭代求出結果。該方法通用性強，但本質上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。 解決方法： 在遞歸算法中消除遞歸調用，使其轉化為非遞歸算法。 } } 遞歸小結 優(yōu)點： 結構清晰，可讀性強，而且容易用數(shù)學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。 move(a,b)。由此可以設計出解 Hanoi塔問題的遞歸算法如下。此時若能設法將 n1個較小的圓盤依照移動規(guī)則從塔座 a移至塔座 c，然后，將剩下的最大圓盤從塔座 a移至塔座 b，最后，再設法將 n1個較小的圓盤依照移動規(guī)則從塔座 c移至塔座 b。此時，只要將編號為 1的圓盤從塔座 a直接移至塔座 b上即可。 在問題規(guī)模較大時，較難找到一般的方法，因此我們嘗試用遞歸技術來解決這個問題。各圓盤從小到大編號為 1,2,… ,n,現(xiàn)要求將塔座 a上的這一疊圓盤移到塔座 b上，并仍按同樣順序疊置。 遞歸的概念 例 6 Hanoi塔問題 設 a,b,c是 3個塔座?？梢越?q(n,m)的如下遞歸關系。 ???????????????????11,1),()1,()1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq 遞歸的概念 例 5 整數(shù)劃分問題 前面的幾個例子中，問題本身都具有比較明顯的遞歸關系，因而容易用遞歸函數(shù)直接求解。 在本例中，如果設 p(n)為正整數(shù) n的劃分數(shù)，則難以找到遞歸關系，因此考慮增加一個自變量：將最大加數(shù) n1不大于 m的劃分個數(shù)記作 q(n,m)。 正整數(shù) n的劃分由 n1=n的劃分和 n1≤n 1的劃分組成。 正整數(shù) n的最大加數(shù) n1不大于 m的劃分由 n1=m的劃分和 n1≤n 1 的劃分組成。 (1) q(n,1)=1,n?1。 最大加數(shù) n1實際上不能大于 n。 例如正整數(shù) 6有如下 11種不同的劃分： 6； 5+1； 4+2， 4+1+1； 3+3， 3+2+1， 3+1+1+1； 2+2+2， 2+2+1+1， 2+1+1+1+1； 1+1+1+1+1+1。 正整數(shù) n的這種表示稱為正整數(shù) n的劃分。 R的全排列可歸納定義如下： 當 n=1時， perm(R)=(r)，其中 r是集合 R中唯一的元素； 當 n1時， perm(R)由 (r1)perm(R1)， (r2)perm(R2)， … ，(rn)perm(Rn)構成。 集合 X中元素的全排列記為 perm(X)。 遞歸的概念 例 4 排列問題 設計一個遞歸算法生成 n個元素 {r1,r2,… ,rn}的全排列。對于通常所見到的正整數(shù) n，有 α(n)≤4 。即 α(n) 是使 n≤A(k) 成立的最小的 k值。 ?n2222? 遞歸的概念 例 3 Ackerman函數(shù) ? 定義單變量的 Ackerman函數(shù) A(n)為， A(n)=A(n，n)。 遞歸的概念 例 3 Ackerman函數(shù)