【正文】 件 遞歸方程 110)2()1(11)(????????????nnnnFnFnF第 n個 Fibonacci數(shù)可遞歸地計算如下： int fibonacci(int n) { if (n = 1) return 1。用函數(shù)自身給出定義的函數(shù)稱為 遞歸函數(shù) 。如果子問題的規(guī)模仍然不夠小，則再劃分為 k個子問題，如此遞歸的進行下去，直到問題規(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) 將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。這自然導致遞歸過程的產(chǎn)生。 Ackerman函數(shù) A(n， m)定義如下： ?????????????????1,20)1),1((),(2)0,(1),0(2)0,1(mnnmmmnAAmnAnnAmAA 遞歸的概念 例 3 Ackerman函數(shù) 前 2例中的函數(shù)都可以找到相應的非遞歸方式定義： nnn ??????? )1(321! ????????????????? ?????????? ???? 1125125151)(nnnF本例中的 Ackerman函數(shù)卻無法找到非遞歸的定義。但在理論上 α(n) 沒有上界，隨著 n的增加，它以難以想象的慢速度趨向正無窮大。求正整數(shù) n的不 同劃分個數(shù)。 (3) q(n,n)=1+q(n,n1)。 正整數(shù) n的劃分數(shù) p(n)=q(n,n)。 當 n＞ 1時，需要利用塔座 c作為輔助塔座。 缺點： 遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。 因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。這種使子問題規(guī)模大致相等的做法是出自一種 平衡(balancing)子問題 的思想，它幾乎總是比子問題規(guī)模不等的做法要好。無論是在前面還是后面查找 x，其方法都和在 a中查找 x一樣，只不過是查找的規(guī)?？s小了。 x, int l, int r) { while (r = l){ int m = (l+r)/2。 大整數(shù)的乘法 請設計一個有效的算法，可以進行兩個 n位大整數(shù)的乘法運算 ?小學的方法： 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()(??????? nnnOnTOnT大整數(shù)的乘法 請設計一個有效的算法，可以進行兩個 n位大整數(shù)的乘法運算 ?小學的方法： O(n2) ?效率太低 ?分治法 : XY = ac 2n + (ad+bc) 2n/2 + bd 為了降低時間復雜度，必須減少乘法的次數(shù)。 ???????????????????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/(8)1()(2 ??????? nnnOnTOnTStrassen矩陣乘法 ?傳統(tǒng)方法 ： O(n3) ?分治法 : O() ?更快的方法 ?? ?Hopcroft和 Kerr已經(jīng)證明 (1971)，計算 2個２ ２矩陣的乘積， 7次乘法是必要的。為了將這 3個無特殊方格的子棋盤轉化為特殊棋盤，可以用一個 L型骨牌覆蓋這 3個較小棋盤的會合處，如 (b)所示，從而將原問題轉化為 4個較小規(guī)模的棋盤覆蓋問題。 // 覆蓋其余方格 chessBoard(tr, tc, tr+s1, tc+s1, s)。 dc tc + s) // 特殊方格在此棋盤中 chessBoard(tr+s, tc, dr, dc, s)。} } 復雜度分析 T(n)=O(4k) 漸進意義下的最優(yōu)算法 ???????? 00)1()1(4)1()(kkOkTOkT合并排序 基本思想： 將待排序元素分成大小大致相同的 2個子集合，分別對 2個子集合進行排序，最終將排好序的子集合合并成為所要求的排好序的集合。 templateclass Type void QuickSort (Type a[], int p, int r) { if (pr) { int q=Partition(a,p,r)。 Swap(a[i], a[j])。 ji完成 {6, 7, 5, 2, 5, 8} {5, 2, 5} 6 {7, 8} templateclass Type int RandomizedPartition (Type a[], int p, int r) { int i = Random(p,r)。 if (k=j) return RandomizedSelect(a,p,i,k)。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共 ?n/5?個。 Type Select(Type a[], int p, int r, int k) { if (rp75) { 用某個簡單排序算法對數(shù)組 a[p:r]排序 。 if (k=j) return Select(a,p,i,k)。此時，S中的 n個點退化為 x軸上的 n個實數(shù) x1,x2,…,xn 。 從而我們用線性時間就可以將 S1的解和 S2的解合并成為 S的解 。由此可以推出 矩形 R中最多只有 6個 S中的點 。 ?因此，若將 P1和 P2中所有 S中點按其 y坐標排好序，則對 P1中所有點，對排好序的點列作一次掃描，就可以找出所有最接近點對的候選者。 設 P1是 S1中距垂直分割線 l的距離在 dm之內的所有點組成的集合； P2是 S2中距分割線 l的距離在 dm之內所有點組成的集合； 將 P1和 P2中點依其 y坐標值排序； 并設 X和 Y是相應的已排好序的點列； 通過掃描 X以及對于 X中每個點檢查 Y中與其距離在 dm之內的所有點 (最多 6個 )可以完成合并； 當 X中的掃描指針逐次向上移動時， Y中的掃描指針可在寬為 2dm的區(qū)間內移動； 設 dl是按這種掃描方式找到的點對間的最小距離； d=min(dm,d