五大常用算法之分治法

柔情只为你懂 2022-08-24 06:06 180阅读 0赞

看了 [五大常用算法之一][Link 1]这篇博文，感觉理解了很多，可是纯粹都是理论，缺少一些示例，所以准备综合一篇博文，以帮助自己记忆，原文：

[http://www.cnblogs.com/steven\_oyj/archive/2010/05/22/1741370.html][Link 1]

**一、基本思想及策略**

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

--------------------

**二、分治法适用的情况**

分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

**第二条特征是应用分治法的前提**它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

**第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征**，如果**具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法**。

**第四条特征涉及到分治法的效率**，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但**一般用动态规划法较好**。

三、示例

（1）基于二分查找方法的插入排序(最坏情况Θ(nlogn) ）

**\[cpp\]**  [view plain][] [copy][view plain] [print][view plain] [?][view plain]

1.  /\* 
2.      将值A\[r+1\]插入A\[p....r\]的非降序序列中  利用的是二分查找方法来插入 
3.  \*/  
4.    
5.  **void** Insertion(**int** A\[\], **int** p, **int** r)  
6.  \{  
7.      **int** i;  
8.      **int** value = A\[r+1\];  
9.      **int** loc = BinaryLocation(A, p, r, value);   //自loc(包括loc)之后的元素全部向后移一位  
10.     **for** (i = r; i >= loc; i--)  
11.     \{  
12.         A\[i+1\] = A\[i\];  
13.     \}  
14.     A\[loc\] = value;  
15. \}  
16.   
17. /\* 
18.     插入排序  两种实现方式 
19. \*/  
20.   
21. **void** InsertionSort(**int** A\[\], **int** p, **int** r)  
22. \{  
23.   
24.    /\*\*\*\*\*\*\*\*\*迭代实现\*\*\*\*\*\*\*\*\*/  
25.     //int i;  
26.   
27.     //for (i = p; i < r; i++)  
28.     //\{   
29.     //  Insertion(A, p, i);  
30.     //\}  
31.   
32.     /\*\*\*\*\*\*\*递归实现\*\*\*\*\*\*\*\*\*/  
33.     **if** (r >= p)  
34.     \{  
35.         InsertionSort(A, p, r-1);  
36.         Insertion(A, p, r-1);  
37.     \}  
38. \}

（2） 大整数乘法

书上讲述的是2个位数都为n位的数相乘，我这里扩展一下，写一个更为一般的方法，任意位数的2个数相乘：  
  
对于任意位数的2个数相乘a \* b，写成：  
  
a  =  a1 \* 10^(n1/2)   +  a0　　　　　　-----n1为a的位数

b  =  b1 \* 10^(n2/2)  +  b0　　　　　　-----n2为b的位数  
  
分治策略就是基于以上变换，将a，b写成前一半数字和后一半数字相加的形式，例如若a = 5423678，那么a1 = 542，a0 = 3678（注意若不是偶数截取较小一半）  
  
这样a和b相乘就可以写为：a \* b = \{  a1 \* 10^(n1/2)   +  a0  \}   \*  \{  b1 \* 10^(n2/2)  +  b0 \}  
  
展开后整理得： a  \*  b  =  a1\*b1 \* 10^\[ (n1+n2)/2 \]   +  a1\*b0 \* 10^(n1/2)   +   a0\*b1 \* 10^(n2/2)  + a0\*b0　　四项  
  
这样就很容易递归的来求a \* b，如果你嫌分解后的数还太大，就可以继续分解。（你可以自己规定在何时结束递归）  
  
  
实现方法：我们定义一个支持方法Mul(String s1,String s2)，用于在结束递归时（在本例中，我定义有一个数是1位时结束递归，直接用普通乘法）计算两个字符串的乘积（为了表示大数，用字符串来接受参数）。有了这个支持方法，分治递归实现两个大数乘法的实现如下：

public static long Mutiply(String a,String b)//用字符串读入2个大整数
        {
            long result = 0;
            if(a.length() == 1 || b.length() == 1)    //递归结束的条件
                result =  Mul(a,b);
            else            //如果2个字符串的长度都 >= 2
            {
                String a1 = a.substring(0, a.length() / 2 );        //截取前一半的字符串(较短的一半)
                String a0 = a.substring(a1.length(), a.length());    //截取后一半的字符串
                //System.out.println(a1);
                //System.out.println(a0);
                String b1 = b.substring(0, b.length() / 2);
                String b0 = b.substring(b1.length(), b.length());
                
                //分治的思想将整数写成这样： a = a1 * 10^(n1/2) + a0, b = b1 * 10^(n2/2)，相乘展开得到以下四项
                //其中n1，n2为2个整数a，b的位数
                result = (long) (Mutiply(a1,b1) * Math.pow(10, a0.length() + b0.length())
                + Mutiply(a1,b0) * Math.pow(10, a0.length()) + Mutiply(a0,b1) * Math.pow(10, b0.length())
                + Mutiply(a0,b0));
            }
            
            return result;
        }

[Link 1]: http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html
[view plain]: http://blog.csdn.net/zabery/article/details/6618353#