遞歸與分治策略第一部分

1、算法設(shè)計與分析,第2章 遞歸與分治策略,分治（Divide and Conquer）,凡治眾如治寡，分數(shù)是也。 孫子兵法,治理大軍團就象治理小部隊一樣有效，是依靠合理的組織、結(jié)構(gòu)、編制。,將一個難以直接解決的大問題，合理分割成一些規(guī)模較小的相同問題，以便各個擊破，這個策略就叫分而治之（分治法）。,第2章 遞歸與分治策略,分治法是最為重要的算法設(shè)計方法之一。 主要思想是：將一個問題不斷分割成若干個小問題，然后通過對小問題的求解再生成大問題的解。 因此分治法可以分為兩個重要步驟： （1）自頂向下：將問題不斷分割成小的問題。 （2）自底而上：將小問題解決來構(gòu)建大問題的解。 分治和遞歸經(jīng)常同時應(yīng)用在算

2、法設(shè)計中。,第2章 遞歸與分治策略,將要求解的較大規(guī)模的問題分割為 k 個較小規(guī)模的子問題。對這 k 個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為 k 個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。,第2章 遞歸與分治策略,將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。,第2章 遞歸與分治策略,【例】找一組數(shù)的最大最小數(shù)。 直接求解：需要 n - 1 次比較來求最小數(shù)（n 個數(shù)兩兩比較共需要 n 1 次），然后另外 n - 2 次比較來求最大數(shù)（除去最小值的剩下 n 1 個數(shù)兩兩比較共需要 n 2 次）。總計為（ 2n

3、- 3）次。 分治方法 （Divide and Conquer）: （1）將數(shù)據(jù)集 S 均分為 S1 和 S2； （2）求解 S1 和 S2 中的最大和最小值； （3）最終的最大和最小值可以計算得到：min( S1, S2 ), max( S1, S2 )； （4）采用同樣的處理方法遞歸處理 S1 和 S2。,第2章 遞歸與分治策略,min_max(S, min, max) if |S| = 2 then min min(S) max max(S) else split S evenly into S1 and S2 min_max(S1, min1, max1) min_max(S2, mi

4、n2, max2) min min(min1, min2) max max(max1, max2) ,治,分,合并,算法描述（為方便起見，假定 n 是 2 的指數(shù)倍，n 1）：,第2章 遞歸與分治策略,復(fù)雜度公式 T( n ) = 3n/2 2 的推導(dǎo)過程（要會處理類似的問題）：,第2章 遞歸與分治策略,第2章 遞歸與分治策略,教學(xué)內(nèi)容和要求（講授 6 學(xué)時，2 學(xué)時上機實驗，共 8 學(xué)時） （1）遞歸、遞歸算法的設(shè)計（Ackerman 函數(shù)、排列問題、整數(shù)劃分問題）（重點） （2）分治法的基本思想、算法效率分析（掌握） （3）二分搜索技術(shù)（熟練掌握） （4）棋盤覆蓋（理解） （5）合并排序（

5、理解） （6）快速排序（熟練掌握）,第2章 遞歸與分治策略,2.1 遞歸的概念 （1）直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。 （2）由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。 （3）分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。,第2章 遞歸與分治策略,遞歸實例 （1）數(shù)據(jù)結(jié)構(gòu)本身固有遞歸特性，特別適于用遞歸描述：樹（二叉樹） 樹是由 n（n 0）個

6、結(jié)點組成的有限集合。若 n = 0，稱為空樹；若 n 0，則： （A）有一個特定的稱為根（root）的結(jié)點。它只有直接后繼，但沒有直接前驅(qū)； （B）除根結(jié)點以外的其它結(jié)點可以劃分為m（ m 0）個互不相交的有限集合T0，T1，Tm-1，每個集合Ti（i = 0, 1, , m - 1）又是一棵樹，稱為根的子樹，每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有 0 個或多個直接后繼。 由此可知，樹的定義是一個遞歸的定義，即樹的定義中又用到了樹的概念。,第2章 遞歸與分治策略,樹的實例 1 - 紅樓夢人物關(guān)系表,樹的實例 2 圖像處理類譜系,第2章 遞歸與分治策略,二叉樹是 n（n 0）個結(jié)點的有限

7、集，它或者是空集（n = 0），或者由一個根結(jié)點及兩棵不相交的左子樹和右子樹組成。,二叉樹的前序遍歷 遞歸算法,第2章 遞歸與分治策略,（2）一些問題本身沒有明顯的遞歸結(jié)構(gòu)，但用遞歸技術(shù)來求解，可使設(shè)計出的算法簡捷易懂。 【例 1】階乘函數(shù) 階乘函數(shù)可遞歸地定義為：,邊界條件（一般是非遞歸定義的初始值）與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(jié)果。,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,int factorial( int n ) if ( n = 0 ) return 1; return n * factorial( n 1 ); ,算法

8、代碼,第2章 遞歸與分治策略,【例 2】 Fibonacci 數(shù)列 無窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為 Fibonacci數(shù)列。它可以遞歸地定義為：,第2章 遞歸與分治策略,第 n 個 Fibonacci 數(shù)可遞歸地計算如下： int fibonacci( int n ) if (n = 1) return 1; return fibonacci( n 1 ) + fibonacci( n 2 ); ,算法代碼,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,【例 3】 Ackerman 函數(shù) 當(dāng)一個函數(shù)及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是雙遞歸函數(shù)。 Ac

9、kerman 函數(shù) A(n，m) 有 2 個獨立的整型變量 m = 0 和 n = 0，定義如下：,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,Ackerman 函數(shù)的特點：“階乘函數(shù)”和“Fibonacci 數(shù)列”都可以找到相應(yīng)的非遞歸方式定義，如下：,Ackerman 函數(shù)卻無法找到非遞歸的定義。,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,Ackerman 函數(shù) A ( n，m ) 的自變量 m 的每一個值都定義了一個單變量函數(shù)：,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,Ackerman 函數(shù)總結(jié)如下：,西安郵電大學(xué)計算機學(xué)

10、院,第2章 遞歸與分治策略,int Ackerman( int n, int m ) if ( m = 0) if ( n = 1 ) return 1; else return ( n + 2 ); else if( n = 0 ) return 1; else return Ackerman( Ackerman( n - 1, m ), m - 1 ); ,算法代碼,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,定義單變量的 Ackerman 函數(shù) A(n) 為：A( n ) = A( n，n )。 定義其擬逆函數(shù)(n)為：( n ) = min kA( k ) n 。即 ( n ) 是

11、使 n A( k )成立的最小的 k 值。 A( 0 ) = 1 A( 1 ) = 2 A( 2 ) = 4 A( 3 ) = 16 A( 4 ) = 2 多重冪（其中 2 的層數(shù)為 65536） 可知： ( 1 ) = 0 ( 2 ) = 1 ( 3 ) = ( 4 ) = 2 ( 5 ) = = ( 16 ) = 3 ( n )的增長速度非常緩慢。 ( n )在復(fù)雜度分析中常遇到。對于通常所見到的正整數(shù)n，有 ( n ) 4 。但在理論上( n )沒有上界，隨著 n 的增加，它以難以想象的慢速度趨向正無窮大。,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,【例 4】 排列問題 設(shè)計一個遞

12、歸算法生成 n 個元素 r1, r2, , rn 的全排列。 全排列：從 n 個不同元素中任取m（m n）個元素，按照一定的順序排列起來，叫做從 n 個不同元素中取出 m 個元素的一個排列。當(dāng) m = n 時所有的排列情況叫全排列。 如 1, 2, 3 三個元素的全排列為： 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 共 3！= 3 * 2 * 1 = 6 種排列,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,全排列的遞歸算法設(shè)計 從實際例子中觀察可知： （1） 1 的全排列為：1 （2） 1, 2 的全排列為：1, 2 2, 1 （3）

13、1, 2, 3 的全排列為： 1, 2, 3 1, 3, 2 2, 3 的全排列加上 1 所得 2, 1, 3 2, 3, 1 1, 3 的全排列加上 2 所得 3, 1, 2 3, 2, 1 1, 2 的全排列加上 3 所得 即：3 個元素的全排列問題可轉(zhuǎn)化為求 2 個元素的全排列問題。 . 推廣結(jié)論：n 個元素的全排列問題可轉(zhuǎn)化為求 n - 1 個元素的全排列問題（遞歸設(shè)計）。,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,全排列的遞歸算法 設(shè) R = r1, r2, , rn 是要進行排列的 n 個元素，Ri = R - ri 。 集合 X 中元素的全排列記為 perm( X )。 (

14、 ri )perm( X ) 表示在全排列 perm( X ) 的每一個排列前加上前綴得到的排列。R的全排列可歸納定義如下：,當(dāng) n = 1 時，perm( R ) = ( r )，其中 r 是集合 R 中唯一的元素； 當(dāng) n 1 時，perm( R ) 由 ( r1 )perm(R1)，( r2 )perm(R2)，( rn )perm(Rn)構(gòu)成。,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,全排列的遞歸算法說明示例 設(shè) R = 1, 2, 3 ，則 n = 3，根據(jù)上述算法，產(chǎn)生的全排列為： 1 2, 3 2 3 3 2 （即對集合 2, 3 繼續(xù)執(zhí)行遞歸算法，下同） 2 1, 3

15、1 3 3 1 3 1, 2 1 2 2 1 即 R = 1, 2, 3 產(chǎn)生的全排列為： 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,全排列在 IT 公司的筆試面試中比較熱門，百度、迅雷等大公司的校園招聘以及程序員和軟件設(shè)計師的考試中都考過此題。 如下面的百度、迅雷校招筆試題中的“全排列”： 【題目】用 C+ 寫一個函數(shù), 如 Foo( const char *str ), 打印出 str 的全排列, 如 abc 的全排列: abc, acb, bca, dac, cab, cba。 【分析】

16、根據(jù)上述描述的算法，可知全排列的遞歸實現(xiàn)算法的規(guī)律是“全排列是從第一個數(shù)字起每個數(shù)分別與它后面的數(shù)字交換”。這樣根據(jù)上述算法可以 寫出示例代碼如下：,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,/ 全排列的遞歸實現(xiàn)（假定集合中的各個元素互不相同） #include #include void Swap( char *a, char *b ) char t = *a; *a = *b; *b = t; ,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,/ k 表示當(dāng)前選取到第幾個數(shù), m表示共有多少數(shù). void AllRange(char *pszStr, int k, int m) if

17、 ( k = m ) static int s_i = 1; printf( 第%3d個排列t%sn, s_i+, pszStr); else for (int i = k; i = m; i+) / 第 i 個數(shù)分別與它后面的數(shù)字交換就能得到新的排列 Swap( pszStr + k, pszStr + i ); AllRange( pszStr, k + 1, m ); Swap( pszStr + k, pszStr + i ); ,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,void Foo( char *pszStr ) AllRange( pszStr, 0, strlen(

18、pszStr ) 1 ); int main() printf( 全排列的遞歸實現(xiàn)n); char szTextStr = 123; printf(%s的全排列如下:n, szTextStr); Foo( szTextStr ); return 0; ,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,運行結(jié)果如下：,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,【例 5】整數(shù)劃分問題 將正整數(shù) n 表示成一系列正整數(shù)之和：n = n1 + n2 + + nk， 其中 n1 n2 nk 1，k 1。 正整數(shù) n 的這種表示稱為正整數(shù) n 的劃分。求正整數(shù)n的不同劃分個數(shù)。 例如正整數(shù) 6 有如

19、下 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,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,再如正整數(shù) 4 有如下 5 種不同的劃分： 4； 3 + 1； 2 + 2，2 + 1 + 1； 1 + 1 + 1 + 1 注意 4 = 1 + 3 和 4 = 3 + 1 被認為是同一個劃分。 也可以采用如下方式表示 4 的 5 個劃分： 4 , 3, 1 , 2, 2 ,

20、2, 1, 1 , 1, 1, 1, 1 ;,第2章 遞歸與分治策略,將正整數(shù) n 的不同劃分個數(shù)稱為正整數(shù) n 的劃分數(shù)，記作 p( n )。如上述 p( 6 ) = 11。 將正整數(shù) n 表示成一系列正整數(shù)之和：n = n1 + n2 + + nk， 其中 n1 n2 nk 1，k 1。正整數(shù) n 的這種表示稱為正整數(shù) n 的劃分。 如果 max n1, n2, , nk = m，則稱劃分 n = n1 + n2 + + nk 屬于 n 的一個 m 劃分，記為 q( n, m )。顯然對于正整數(shù)劃分問題而言，m = n，即計算 q( n, n ) 的值。 前面的幾個例子中，問題本身都具有比

21、較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè) p( n ) 為正整數(shù)n的劃分數(shù)，則難以找到遞歸關(guān)系。需要借助 q( n, m ) 建立遞歸關(guān)系。,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,在這里考慮一般的 q( n, m ) 的計算，根據(jù) n 和 m 的關(guān)系，考慮以下幾種情況： （1）當(dāng) n = 1 時，不論 m 的值為多少( m 0 )，只有一種劃分即 1 ; （2）當(dāng) m = 1 時，不論 n 的值為多少，只有一種劃分即 n 個 1， 1, 1, 1, ., 1 ;,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,（3） 當(dāng) n = m 時，根據(jù)劃分中是否包含 n，

22、可以分為兩種情況： （3-1）劃分中包含 n 的情況，只有一個即 n ； （3-2）劃分中不包含 n 的情況，這時劃分中最大的數(shù)字也一定比 n 小，即 n 的 所有 ( n 1 ) 劃分。（ m = n 1，即包含所有max n1, n2, , nk = n 1 的情況） 因此 q( n, m ) = q( n, n ) = 1 + q( n, n 1 ); 注意：q( n, m ) 中 m 的定義為： 如果 max n1, n2, , nk = m，則稱劃分 n = n1 + n2 + + nk 屬于 n 的一個 m 劃分，記為 q( n, m )。 當(dāng) n = m 時， max n1, n

23、2, , nk = m = n，也即 n1, n2, , nk 中的最大值小于或者等于 n 都是可以的，所以上述（3-2）是成立的。,第2章 遞歸與分治策略,（4）當(dāng) n m 時，根據(jù)劃分中是否包含最大值 m，可以分為兩種情況： （5-1）劃分中包含 m 的情況，即 m, n1, n2, ., ni , 其中 n1, n2, ., ni 的和 為 n - m，可能再次出現(xiàn) m（ max n1, n2, , ni = m 是可以成立的）， 因此是（ n - m）的 m 劃分，因此這種劃分個數(shù)為 q( n - m, m ); （5-2）劃分中不包含 m 的情況，則劃分中所有值都比 m ?。?m），

24、即 n 的 ( m 1 ) 劃分（一定滿足max n1, n2, , nk = m - 1），個數(shù)為 q( n, m 1 ); 因此 q( n, m ) = q( n - m, m ) + q( n, m 1 );,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,綜上可知：上面的結(jié)論具有遞歸定義特征，其中（1）和（2）屬于回歸條件，（3）和（4）屬于特殊情況，將會轉(zhuǎn)換為情況（5）。而情況（5）為通用情況，屬于遞推的方法，其本質(zhì)主要是通過減小 m 以達到回歸條件，從而解決問題。 遞推表達式如下：,正整數(shù) n 的劃分數(shù) p( n ) = q( n, n )。,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與

25、分治策略,因此可以給出求出 q( n, m ) 的遞歸函數(shù)代碼如下： unsigned long GetIntegerPartitionCount( int n, int m ) if ( n = 1 | m = 1 ) return 1; else if ( n m ) return GetIntegerPartitionCount( n, n ); else if ( n = m ) return 1 + GetIntegerPartitionCount( n, m 1 ); else return GetIntegerPartitionCount( n, m 1 ) + GetInteg

26、erPartitionCount( n - m, m ); ,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,【例 6】Hanoi 塔問題 一位法國數(shù)學(xué)家曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大到小的 64 片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。,漢

27、諾塔益智玩具,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,如果考慮一下把 64 片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。這需要多少次移動呢? 這里需要遞歸的方法。假設(shè)有 n 片，移動次數(shù)是f( n ).顯然 f( 1 )=1, f( 2 ) = 3, f( 3 ) = 7，且 f( k+1 ) = 2 * f( k ) + 1。此后不難證明 f( n ) = 2 n - 1。n = 64 時，假如每秒鐘一次，一年 365 天有 31536000 秒，閏年 366 天有 31622400 秒，平均每年 31556952 秒，計算一下， 18446744073709551

28、615 / 31556952 = 584554049253.855年 這表明移完這些金片需要5845億年以上，而地球存在至今不過 45 億年，太陽系的預(yù)期壽命據(jù)說也就是數(shù)百億年。真的過了5845億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經(jīng)灰飛煙滅。,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,Hanoi 塔問題的標(biāo)準(zhǔn)描述： 設(shè) a, b, c 是 3 個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則： 規(guī)

29、則 1：每次只能移動 1 個圓盤； 規(guī)則 2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則 3：在滿足移動規(guī)則 1 和 2 的前提下，可將圓盤移至 a,b,c 中任一塔座上。,Hanoi 塔的動態(tài)演示,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,算法設(shè)計： （1）當(dāng) n = 1 時，只要將編號為 1 的圓盤從塔座 a 直接移到塔座 b 上即可； （2）當(dāng) n 1 時，需要利用塔座 c 作為輔助塔座。此時要設(shè)法將 n - 1 個較小的圓盤依照規(guī)則從 a 移至 c 上，然后將剩下的最大塔座從 a 移至 b 上。最后設(shè)法將 n - 1 個較小的圓盤依照規(guī)則從 c 移至 b 上。 由此可

30、見，n 個圓盤的移動問題可分解為兩次 n - 1 個圓盤的移動問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計出算法如下：,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,void hanoi( int n, int a, int b, int c ) / 將塔座 a 上的 n 個圓盤依規(guī)則移至塔座 b 上， / 以塔座 c 作為輔助塔座 if ( n 0 ) hanoi( n - 1, a, c, b ); move( a, b ); / 將塔座 a 上編號為 n 的圓盤移至塔座 b 上 hanoi( n - 1, c, b, a ); ,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,遞歸

31、小結(jié) 優(yōu)點：結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。 缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。 解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。 （1）采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。 （2）用遞推來實現(xiàn)遞歸函數(shù)。這種方法在時空復(fù)雜度上均有較大改善，但其適用范圍有限。,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,2.2 分治法的基本思想 分治法的基本思想是將一個規(guī)模為 n

32、的問題分解為 k 個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。 分治法所能解決的問題一般具有以下幾個特征： （1）該問題規(guī)?？s小到一定的程度就可以容易地解決； 因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有“最優(yōu)子結(jié)構(gòu)性質(zhì)”。 這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用。 （3）利用該問題分解出的子問題的解可以合并為該問題的解。 能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃。,西安郵電大學(xué)計算機學(xué)院,第2章 遞歸與分治策略,（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。,西安郵電大學(xué)計算機學(xué)院,第2章