抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >
This is a picture without description

常用算法系列1一分治算法及其应用

Algorithm

发布：2021年1月11日

更新：2021年1月11日
次浏览

最近在准备算法设计与分析的期末考试，顺便简单总结记录一下。Let’s go~~~

image

前言

    在正式开始某一具体算法之前，还是想简单废话一下自己对算法的理解和认识。首先，三大本源问题：算法是什么？为什么会有算法？常用的算法都有哪些且它们都能用来解决什么样的问题？

    余以为，算法，就是解决问题时所用的指定的方法和步骤，通过这个步骤和方法能够得到这个问题的答案。我们一直在用算法，我们身边都是算法，只是在这里，我们是从计算机科学的角度去讨论某些常用的算法。

    为什么会有算法？因为我们的身边总是存在各种各样的问题需要去解决，每个人都有或没有自己解决问题的思维思想，但自己的思想可能不是最好最优的算法，所有我们要站在巨人的肩膀上，总结和归纳比较好的思想，通过学习优秀的思想，解决对应的问题，也是扩展开发自己的思维，因而存在需要学习的算法。

    常用的算法思想主要有：迭代、分治、贪心、动态规划、回溯、分支限界等，每一种算法思想都可以用来解决不同的或相同的问题，因为存在不同特性和优劣的问题，需要根据不同的情况来选择最优的算法。

    迭代适合问题规模比较小，能够验证最优解的情况；分治适合规模大且具有相同子问题的情况，将大问题分割为小问题解决；贪心适合问题整体的规模不是由局部最优解组成，且对最优解没有要求的情况；动态规划适合当问题的整体最优解就是由局部最优解组成的情况；回溯适合具有尝试性的问题，利用dfs的思想不能得到则回退；分支限界适合产生多个子结构并从中选择最优而同时排除非最优的子结构的问题，能够加速收敛得到最优解。

大白话，真的是有够抽象的，难以描述。

那么，为了拥有更好的解决问题或得到更好答案的思想，现在从分治算法开始👇👇

一、分而治之算法

    **分而治之算法(divide and conquer)**，就是把一个复杂的问题分成两个或多个相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。另外，因为分治的子问题的属性，所以它常常与递归相伴 ——分治算法—WIKI

概念过于空泛，来点典型应用👇👇

二、分治算法的典型应用

1. 二分查找

    二分查找：说到分治，那必须点到二分查找。二分查找Binary Search，也称“折半查找”“对数搜索”，就是在一个有序的数组中查找某一特定元素的算法，通过比较与中间值的大小，不断缩小查找的范围。这就应用了分治的思想，从大数组逐步变成小数组，最后得到问题的解。——二分查找算法—WIKI

[WIKI的图](https://zh.wikipedia.org/wiki/File:Binary_search_into_array.png)

顺便实现下？😏😏

BinarySearch 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
   * 递归二分
   * @param arr
   * @param left
   * @param right
   * @param target
   * @return
   */
  int binarySearch(int arr[], int left, int right, int target) {
      if (left > right)
          return -1;

      int mid = left + (right - left) / 2;// 避免溢出不使用直接平均

      if (arr[mid] == target) {
          return mid;
      } else if (arr[mid] < target) {
          return binarySearch(arr, mid + 1, right, target);
      } else {
          return binarySearch(arr, left, mid - 1, target);
      }
  }

/**
   * 非递归二分
   * @param arr
   * @param target
   * @return
   */
  int UnRecursionBinarySearch(int[] arr, int target) {
      int left = 0;
      int right = arr.length;

      while (left <= right) {
          int mid = left + (right - left) / 2;// 避免溢出不使用直接平均

          if (arr[mid] == target) {
              return mid;
          } else if (arr[mid] < target) {
              left = mid + 1;
          } else {
              right = mid - 1;
          }
      }
      return -1;
  }

时间复杂度O(logN) ：折半，每次少一半，2^x = N ，总次数为x。

空间复杂度O(1) ：固定大小数组，固定次数的临时变量。

2. 快速排序

    快速排序：有查找，怎么能没有排序？当然，主要还是快排确实用到了分治的思想。快速排序Quick Sort，又称分区交换排序（partition-exchange sort），简称快排，快排的主要实现思想是以某一值为标准，比这个值小的放左边，比这个值大的放右边，这样就排序完了一个值，左边的值都比它小，右边的值都比它大。然后再对这两个子集合进行同样的算法排序，直到最后两个子集合也排序完，那么整个排序也就排完了。————快速排序-WIKI

[WIKI的图](https://zh.wikipedia.org/wiki/File:Sorting_quicksort_anim.gif)

顺便实现下？😏😏

Inplace-QuickSort 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
    * 快速排序 按照设计的算法思想，先把快排大问题化小问题的大框架搭起来
    * 
    * @param arr
    * @param left
    * @param right
    */
   void quickSort(int[] arr, int left, int right) {

       if (left > right)
           return;

       // 取中间值，暂时不用管怎么取，就是partition()给的
       int mid = partition(arr, left, right);

       // 同样算法排左边的子集合
       quickSort(arr, left, mid-1);

       // 同样的算法排右边的子集合
       quickSort(arr, mid + 1, right);
       // 左右的子集合都排完之后就排好了，框架搭建完毕。
   }

   /**
    * 分区，取基准值
    * 然后再取基准值，在进行左右大小分区后得到基准值，本方法做的就是分区
    * @param arr
    * @param left
    * @param right
    * @return
    */
   int partition(int[] arr, int left, int right) {

       int mid = arr[left];

       // 不断筛选
       while (left < right) {

           // 从右边开始，找一个小的用来替换到左边
           while (left < right && arr[right] >= mid) {
               right--;
           }
           if (left < right) {
               arr[left] = arr[right];
           }

           // 从左边找一个大的用来换到右边
           while (left < right && arr[left] <= mid) {
               left++;
           }
           if (left < right) {
               arr[right] = arr[left];
           }

       }
       arr[left] = mid;

       return left;
   }

时间复杂度O(？) : 等一位高人指点，please。

空间复杂度O(1) ：一个数组原地排序，三个临时变量。

3. 归并排序

    归并排序：有快排，当然少不了归并咯。归并排序Merge Sort，指将两个已经排序的序列合并成一个序列的操作，该算法依赖于归并操作。其实它包含分治算法的两个步骤：1.分割——一个大序列分成只有一个或两个元素的小序列；2.集成：保持元素顺序同时将上一步得到的小序列合并到一起。u1s1，归并真是把分治的思想体现得淋漓尽致，先是大化小，再小化大而得到解。————归并排序-WIKI

[WIKI的图](https://zh.wikipedia.org/wiki/File:Merge-sort-example-300px.gif)

顺便实现下？😏😏

MergeSort 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
  * 此方法用来简化方法调用，只需传入要排序的数组即可
  * 
  * @param arr
  */
 void faMergeSort(int[] arr) {
     int[] temp = new int[arr.length];// 临时数组，辅助存储交换的数据
     mergeSort(arr, 0, arr.length - 1, temp);// 调用真正的归并方法
 }

 /**
  * 实现了归并算法的方法——分解
  * 
  * @param arr
  * @param left
  * @param right
  * @param temp
  */
 void mergeSort(int[] arr, int left, int right, int[] temp) {
     if (left >= right)
         return;
     int mid = left + (right - left) / 2;
     mergeSort(arr, left, mid, temp);// 归并左边
     mergeSort(arr, mid + 1, right, temp);// 归并右边
     mergerSortInOrder(arr, left, mid, right, temp);// 合并左右
 }

 /**
  * 归并的合并实现：将左右子序列按大小存到temp数组，最后再拷贝temp数组中的值覆盖原数组
  * 
  * @param arr
  * @param left
  * @param mid
  * @param right
  * @param temp
  */
 void mergerSortInOrder(int[] arr, int left, int mid, int right, int[] temp) {
     // 利用两个指针，一左一右
     int lp = left;// 左边子序列
     int rp = mid + 1;// 右边子序列
     int tp = 0;// 临时数组的指针

     // 将左右两个序列的值按大小顺序存到临时数组中
     while (lp <= mid && rp <= right) {
         if (arr[lp] <= arr[rp]) {
             temp[tp++] = arr[lp];// 存到临时数组
             lp++;// 下一个值
         } else {
             temp[tp++] = arr[rp];
             rp++;
         }
     }

     // 已经存完了至少一边子序列,看看还有没有剩的数没加进临时数组
     while (lp <= mid) {
         temp[tp++] = arr[lp++];
     }
     while (rp <= right) {
         temp[tp++] = arr[rp++];
     }
     
     // 将临时数组中排好序的数组拷贝回原数组
     tp = 0;
     while (left <= right) {
         arr[left++] = temp[tp++];
     }
 }

4. 斐波那契数列

    斐波那契数列：斐波那契数列也蕴含着分治思想嘛——F(n) = F(n-1) + F(n-2)。自顶向下，大问题化为小问题；回溯求和，小问题的解合并为大问题的解。这里可以看一个例子——下楼梯问题或者同理的leetcode70.爬楼梯问题，本质上与斐波那契数列一样。

下楼梯问题

问题描述：有n阶楼梯要下，一次可以下一阶或两阶。问：下n阶楼梯有几种方案？

注：该问题与爬楼梯问题一样，这里不再赘述。只是若用递归的自顶向下，时间复杂度爆表；更好的方法应该用迭代的自底向上，借助数组记录每一个层数对应的方法。

5. 整数划分

    整数划分：再来看一道典例，整数划分。

三、总结一下

经过上面这么多题的磨练，想必对分治的理解多多少少也有些概念了，这里再来稍微总结一波。

1.算法步骤

由分治算法的思想，可以很容易想到利用递归过程来表示。分治在每一层递归上都有3个步骤（或2个）

  1. 分解：将原问题分解为若干规模较小，相互独立，与原问题形式相同的子问题；
  2. 解决：若子问题规模较小而容易被解决则直接解，否则继续分解为更小的子问题，直到容易解决；
  3. 合并：将已求解的各个子问题的解，逐步合并为原问题的解。

2.算法框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Divide-and-Conquer(n) //n为问题规模
{

  if(n <= n0){        //n0为可解子问题的规模
    /*解子问题*/
    return ("子问题的解");
  }

  for(int i = 0; i <= k; i++){    //分解为较小的k个子问题P1,P2,...,Pk
    /*分解原问题为更小的子问题Pi*/
    yi=Divide-and-Conque(|Pi|);
  }

  T=MERGE(y1,y2,y3,...,yk);//合并子问题

  return(T);
}

参考

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://zy68.top/2021/01/11/divideAndConquer/

algorithm

divide and conquer

评论

Gitalk评论系统对接至Github Issue，随心评论🐾🐾.....