【正文】 成一系列正整數(shù)之和： n=n1+n2+… +nk， 其中 n1≥n 2≥ … ≥n k≥1 ， k≥1 。 設(shè) R={r1,r2,… ,rn}是要進(jìn)行排列的 n個(gè)元素， Ri=R{ri}。 ? α(n) 在復(fù)雜度分析中常遇到。 ? M=3時(shí)，類似的可以推出 ? M=4時(shí)， A(n,4)的增長(zhǎng)速度非?？?，以至于沒有適當(dāng)?shù)臄?shù)學(xué)式子來表示這一函數(shù)。 return fibonacci(n1)+fibonacci(n2)。 下面來看幾個(gè)實(shí)例。 ? 由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) 算法總體思想 ? 將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。 算法總體思想 ? 對(duì)這 k個(gè)子問題分別求解。 ? （ 1）二分搜索技術(shù)； ? （ 2）大整數(shù)乘法； ? （ 3） Strassen矩陣乘法； ? （ 4）棋盤覆蓋； ? （ 5）合并排序和快速排序； ? （ 6）線性時(shí)間選擇； ? （ 7）最接近點(diǎn)對(duì)問題； ? （ 8）循環(huán)賽日程表。第 2章 遞歸與分治策略 學(xué)習(xí)要點(diǎn) : ? 理解遞歸的概念。 ? 將要求解的較大規(guī)模的問題分割成 k個(gè)更小規(guī)模的子問題。如果子問題的規(guī)模仍然不夠小，則再劃分為 k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) 分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題， 分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破， 分而治之。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。 遞歸的概念 例 1 階乘函數(shù) 階乘函數(shù)可遞歸地定義為： 00)!1(1!???????nnnnn邊界條件 遞歸方程 邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。 } 遞歸的概念 例 3 Ackerman函數(shù) 當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是 雙遞歸函數(shù) 。 ?n2222? 遞歸的概念 例 3 Ackerman函數(shù) ? 定義單變量的 Ackerman函數(shù) A(n)為， A(n)=A(n，n)。對(duì)于通常所見到的正整數(shù) n，有 α(n)≤4 。 集合 X中元素的全排列記為 perm(X)。 正整數(shù) n的這種表示稱為正整數(shù) n的劃分。 最大加數(shù) n1實(shí)際上不能大于 n。 正整數(shù) n的最大加數(shù) n1不大于 m的劃分由 n1=m的劃分和 n1≤n 1 的劃分組成。 在本例中，如果設(shè) p(n)為正整數(shù) n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù) n1不大于 m的劃分個(gè)數(shù)記作 q(n,m)。可以建立 q(n,m)的如下遞歸關(guān)系。各圓盤從小到大編號(hào)為 1,2,… ,n,現(xiàn)要求將塔座 a上的這一疊圓盤移到塔座 b上，并仍按同樣順序疊置。此時(shí)，只要將編號(hào)為 1的圓盤從塔座 a直接移至塔座 b上即可。由此可以設(shè)計(jì)出解 Hanoi塔問題的遞歸算法如下。 } } 遞歸小結(jié) 優(yōu)點(diǎn)： 結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。 遞歸小結(jié) 分治法的適用條件 分治法所能解決的問題一般具有以下幾個(gè)特征： ? 該問題的規(guī)?？s小到一定的程度就可以容易地解決； ? 該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì) ? 利用該問題分解出的子問題的解可以合并為該問題的解； ? 該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。 divideandconquer(P) { if ( | P | = n0) adhoc(P)。即將一個(gè)問題分成大小相等的 k個(gè)子問題的處理方法是行之有效的。再設(shè)將原問題分解為 k個(gè)子問題以及用 merge將 k個(gè)子問題的解合并為原問題的解需用 f(n)個(gè)單位時(shí)間。因此這個(gè)問題滿足分治法的第一個(gè)適用條件 分析： 比較 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即可。 二分搜索技術(shù) 給定已按升序排好序的 n個(gè)元素 a[0:n1]，現(xiàn)要在這 n個(gè)元素中找出一特定元素 x。 據(jù)此容易設(shè)計(jì)出 二分搜索算法 ： templateclass Type int BinarySearch(Type a[], const Typeamp。 else l = m+1。循環(huán)體內(nèi)運(yùn)算需要 O(1) 時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為 O(logn) 。 ?最終的，這個(gè)思想導(dǎo)致了 快速傅利葉變換 (Fast Fourier Transform)的產(chǎn)生。由此可將方程 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) ?分治法 : 為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。 ?在 Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。 特殊方格必位于 4個(gè)較小子棋盤之一中，其余 3個(gè)子棋盤中無特殊方格。 int t = tile++, // L型骨牌號(hào) s = size/2。 else {// 此棋盤中無特殊方格 // 用 t 號(hào) L型骨牌覆蓋右下角 board[tr + s 1][tc + s 1] = t。 dc = tc + s) // 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s)。amp。} // 覆蓋右下角子棋盤 if (dr = tr + s amp。 // 覆蓋其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s)。 mergeSort(a, i+1, right)。 初始序列 [49] [38] [65] [97] [76] [13] [27] [38 49] [65