Skip to main content

分治算法

tip

分治算法本质上也是递归，只不过是表现得比较抽象。

  1. 划分子问题的过程就是在函数里面写递归的函数(自己调用自己)。
  2. 求解就是在满足if的条件准备开始return的时候进行。
  3. 最后合并的时候递归函数对应的那个系统栈出栈返回结果的过程。

基本概念​

分治算法的主要思想是划分子问题、求解子问题、合并所有解。用伪代码进行描述如下:

Divide-and-Conquer(P)   
1.  if  |P| <= c  then  S(P).
2.  divide P into P1, P2, …, Pk. //划分子问题
3.  for i = 1 to k 
4.    yi = Divide-and-Conquer(Pi)  //求解子问题
5．Return Merge(y1, y2, …, yk)  //结果合并

分治算法中子问题和原问题的性质是一样的，也就是相同的一个问题。根据这个特点又可以分为递归型和非递归型分治

  • 主要分为三步骤(分-治-合)

    • 分解子问题(关键步骤，找到一种方式分解子问题，且分解的子问题是性质相同的)
    • 解决子问题
    • 合并子问题的解得原问题的解

  • 一般来说，最常用到的分析方式是递推方程。

  • 求解方法主要有迭代法、递归树、主定理

  • 一般来说，如果子问题和原问题相同，只是规模不同，那么就可以对子问题重复相同的过程。直到子问题可以直接求解。要关注问题要求的东西。要么两个一组，要么分成两块。有的时候可以先用排序，再用高效的算法

实际例子应用​

例:求一个数的幂​

问题: 计算ana^n, nn为自然数

分析

算法核心: 将问题划分成多个子问题，这里是将求解幂这个问题进行拆分(一般都是一分为二)。因为求一个数的幂之后的结果，就是nn个数aa进行相乘。那么我们这样思考:ana^n是由两个数相乘得到的，也就是an=an2×an2a^n=a^{\frac{n}{2}}\times a^{\frac{n}{2}}，所以就可以多次递归求解。把求解ana^n的问题拆分成求an2×an2a^{\frac{n}{2}}\times a^{\frac{n}{2}}，这个步骤需要求解an2a^{\frac{n}{2}}，求解an2a^{\frac{n}{2}}又需要继续往下进行递归，最终递归完之后将所有结果进行合并，就得到了原问题的解。

两两相乘会出现两种情况:

  1. nn是奇数，此时因为是两两之间相乘，奇数必然会多出一个数没乘，所以就变成表达式为an=an−12×an−12×aa^n=a^{\frac{n-1}{2}}\times a^{\frac{n-1}{2}}\times a(先减1变成偶数再乘多一个aa)
  2. nn是偶数，此时因为是两两之间相乘，正好能够得到结果。所以表达式为an=an2×an2a^n=a^{\frac{n}{2}}\times a^{\frac{n}{2}}(直接拆乘两个数相乘)
  • 传统做法:

根据定义做

int main() {
    
    int a, n, sum = 1;
    cin >> a >> n;
    for (int i = 1 ; i <= n ; ++i) {
        sum *= a;
    } 
    cout << sum << endl;
    
    return 0;
}
  • 分治做法:
  int a, n, sum;
  int calc(int a, int n) {
      
      if (n == 1) {
          return pow(a, n) * pow(a, n);
      } else {
          if (n % 2 == 0) {
              sum = calc(a, n/ 2);
          } else {
              sum = calc(a, (n - 1) / 2) * a;
          }
      }
      return sum;
  }
  int main() {
      
      cin >> a >> n;
      sum = calc(a, n);
      cout << sum << endl;
      return 0;
  }

例:计算Fibonacci数​

  • 传统做法:

根据定义做

#include <iostream>
using namespace std;
int main() {
  int a = 0, b = 1, res, n;
  cin >> n;
  if (n == 0) cout << a << endl;
  else if (n == 1) cout << b << endl;
  else {
    for (int i = 1; i <= n ;i ++) {
        res = a + b;
        b = a;
        a = res;
    }
    cout << res << endl;
  }
  return 0;
}

选第k小​

核心思想为采用快排的思想，结合快排进行划分。其实跟排序差不多，但不需要全部排序完

采用快速排序的思想，找到一个基准元素将序列一分为二，跟快排思想类似。 当左边的序列长度为k-1时，那么第k个元素就是所求解，如果左边序列长度小于k-1，则在右边剩下的序列中找第k小的，因为左序列小于k-1说明第k小不在左边，则需要在右边进行查找，此时长度为k-l_len-1。如果左边序列大于k-1，说明第k小的元素一定在左边，查找长度为k.

调高算法效率的途径​

  1. 通过代数变换，减少子问题的个数
  2. 对数据的预处理放到算法之外进行，不要放到算法内部

锦标赛算法​

核心思想: 将序列进行两两为一组，这组每两个数之间做一次比较，找到较大的那个数，将较大的数放到下一次比较，将较小的数进行记录。

快排和归并排序的妙用​

快速排序算法本质上是一个根据需要把区间划分成两个部分，根据某一个值。

如求解使得负数都排在整数前面这个问题，这里是根据0进行划分，将区间分成两半，以后只要是需要将区间进行二分的都可以考虑快排算法的改版（这种情况是分为三个部分，两个区间+一个数）。

如果是要单纯分成两个区间而且这两个区间还要考虑边界值之间的关系，那么可以根据归并排序进行修改。