Go语言视频零基础入门到精通

javalearner

一、分治法的基本思想
    任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。
    例如，对于n个元素的排序问题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3 时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

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

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

     
   
  
   二、分治法的适用条件
分治法所能解决的问题一般具有以下几个特征：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

   上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

三、分治法的基本步骤
分治法在每一层递归上都有三个步骤：
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
（3）合并：将各个子问题的解合并为原问题的解。     根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。 但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。
换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。 分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显， 有些问题合并方法比较复杂，或者是有多种合并方案；或者是合并方案不明显。 究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。

四、例二分检索查找最大值代码

1. /**   
   
2. * 使用分治法的思想查找最大值   
   
3. *   
   
4. * @author Administrator   
   
5. *   
   
6. */   
   
7. public class FindMax {   
   
8.   
   
9.     // 返回最大值的方法   
   
10.     public int returnMax(int array[]) {   
    
11.         int length = array.length;   
    
12.         int first;   
    
13.         int second;   
    
14.         if (length == 1) {   
    
15.             return array[0];   
    
16.         } else if (length == 2) {   
    
17.             return Math.max(array[0], array[1]);   
    
18.         } else if (length < 1) {   
    
19.             return 0;   
    
20.         } else {   //这里将一个数组一分为二，然后各个求解   
    
21.             first = length / 2;   
    
22.             second = length - length / 2;   
    
23.             int firstArray[] = new int[first];   
    
24.             int secondArray[] = new int[second];   
    
25.             for (int i = 0; i < first; i++) {   
    
26.                 firstArray[i] = array[i];   
    
27.             }   
    
28.             for (int j = first; j < length; j++) {   
    
29.                 secondArray[j - first] = array[j];   
    
30.             }   
    
31.             return Math.max(returnMax(firstArray), returnMax(secondArray));   
    
32.         }   
    
33.     }   
    
34.   
    
35.     public static void main(String[] args) {   
    
36.   
    
37.         FindMax findMax = new FindMax();   
    
38.         int array[] = { 5, 12, 1, 36, 9, 2, 14, 30, 21, 56,80,12,33};   
    
39.         long start = System.currentTimeMillis();   
    
40.         int max = findMax.returnMax(array);   
    
41.         long end = System.currentTimeMillis();   
    
42.         System.out.println("这个数组中的最大值是:" + max);   
    
43.         System.out.println("本次查找耗时: " + (end - start) + " ms");   
    
44.     }   
    
45.   
    
46. }  
    

复制代码

运行：
C:java>java FindMax
这个数组中的最大值是:80
本次查找耗时: 0 ms

上面的程序使用二分法查找一个数组的最大值，这是一个简单的程序，但我认为已经能很好的解释分治法的思想了。下面一个程序将通过一个归并排序来进一步说明。这些都只是简单的应用，但是理解了这个思想后，可以在很多实际的应用中让我们的程序变得更加有效。 五、例归并排序算法代码

1. //归并排序   
   
2. public class MergerSort {   
   
3.   
   
4.     public int[] sort(int array[]) throws Exception {   
   
5.   
   
6.         int newArray[];   
   
7.         int length = array.length;   
   
8.         int first, second;   
   
9.         newArray = new int[length];   
   
10.         if (length == 1) {   
    
11.             return array;   
    
12.         } else if (length == 2) {   
    
13.             newArray[0] = Math.min(array[0], array[1]);   
    
14.             newArray[1] = Math.max(array[0], array[1]);   
    
15.             return newArray;   
    
16.         } else {// 这里用到了分治法的思想,将一个数组一分为二   
    
17.             first = length / 2;   
    
18.             second = length - length / 2;   
    
19.             int firstMark = 0;//用来标记第一个数组取到的下标   
    
20.             int secondMark = 0;//用来标记第二个数组取到的下标   
    
21.             int mark = 0;   
    
22.             int firstArray[] = new int[first];   
    
23.             int secondArray[] = new int[second];   
    
24.             for (int i = 0; i < first; i++) {   
    
25.                 firstArray[i] = array[i];   
    
26.             }   
    
27.             for (int j = first; j < length; j++) {   
    
28.                 secondArray[j - first] = array[j];   
    
29.             }   
    
30.             firstArray = this.sort(firstArray);   
    
31.             secondArray = this.sort(secondArray);   
    
32.             while (mark < length) {   
    
33.                 if (firstMark < first && secondMark < second) {   
    
34.                     if (firstArray[firstMark] <= secondArray[secondMark]) {   
    
35.                         newArray[mark] = firstArray[firstMark];   
    
36.                         firstMark++;   
    
37.                     } else {   
    
38.                         newArray[mark] = secondArray[secondMark];   
    
39.                         secondMark++;   
    
40.                     }   
    
41.                 } else if (firstMark < first && secondMark >= second) {   
    
42.                     newArray[mark] = firstArray[firstMark];   
    
43.                     firstMark++;   
    
44.                 } else if (firstMark >= first && secondMark < second) {   
    
45.                     newArray[mark] = secondArray[secondMark];   
    
46.                     secondMark++;   
    
47.                 } else {   
    
48.                     throw new Exception("error");   
    
49.                 }   
    
50.                 mark++;   
    
51.             }   
    
52.         }   
    
53.         return newArray;   
    
54.     }   
    
55.   
    
56.     public static void main(String[] args) {   
    
57.         MergerSort mergerSort = new MergerSort();   
    
58.         int array[] = { 5, 12, 1, 36, 9, 2, 14, 30, 21, 56, 80, 12, 33 };   
    
59.         long start = System.currentTimeMillis();   
    
60.         long end = System.currentTimeMillis();   
    
61.         try {   
    
62.             array = mergerSort.sort(array);   
    
63.         } catch (Exception e) {   
    
64.             e.printStackTrace();   
    
65.         }   
    
66.         System.out.println("排序后的数组为:");   
    
67.         for (int i = 0; i < array.length; i++) {   
    
68.             System.out.print(array[i] + "        ");   
    
69.         }   
    
70.         System.out.println("本次查找耗时: " + (end - start) + " ms");   
    
71.     }   
    
72.   
    
73. }  
    
75. 运行：

复制代码

C:java>java MergerSort
排序后的数组为:
1 2 5 9 12 12 14 21 30 33 36 56 80 本次查找耗时: 0 ms
   

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/26/000603140.zip