算法-分治算法

分治算法

作者：刘楚杰，时间：2022年11月13日

未经本人允许禁止转载

什么是分治算法

• 分治算法，顾名思义，也就是分而治之。
• 分治算法通常会将一个问题分割成几个子问题，我们在假设子问题已经处理好的情况下处理该问题，或者先将该问题处理完成后再去处理子问题。比如：假设我们要找一排人中最高的那个，我们可以先将这些人分成两部分，假设两部分中最高的那个我们都已经知道了，那么我们只需要将这两个人比一下身高，返回最大的那个即可。

分治算法的优点

• 分治算法可以只对当前问题进行考虑，无需考虑子问题（假设子问题已经处理好，或者先将该问题处理好之后我们再递归去处理子问题）
• 减小代码量，我们无需将每一步的问题都写出来，因为分治算法的子问题与该问题相同，因此我们只需要递归使用同一个函数即可
• 分治算法可以尝试将$\Theta (n^2)$的时间复杂度降低为$\Theta (nlo{g}_{2}n)$，也可以尝试将$\Theta (n)$的时间复杂度降低为$\Theta (lo{g}_{2}n)$

分治算法的核心思想

• 分治算法将一个问题分成多个相同的子问题，子问题遇到的情况与该问题遇到的情况相同，我们可以先递归解决子问题，然后在子问题已经解决的基础上解决该问题；我们也可以先对该问题进行处理，然后再去处理子问题。
• 分治算法与动态规划有些类似，重点在于找到相同的子问题，或者自行构造相同的子问题。

分治算法的技巧

• 分治算法的一种解题方式：
  • 仅考虑左半部分的最优解
  • 仅考虑右半部分的最优解
  • 考虑横跨左半部分与右半部分的最优解：
    • 左边取一个元素，右边取一个元素，然后考虑这两个元素组成的区间（横跨了mid）的最优解，然后将之分别与左半部分和右半部分的最优解比较
    • 横跨mid的这一部分通常不再进行递归、分治
  • 返回当前最优解

常见的分治算法通常将一个问题平分为两个子问题，然后先解决两个子问题，再来处理当前问题。

• 如果分治算法涉及到区间，我们可以直接使用一个全局变量来记录整体的区间，然后在分治的过程中只需使用左右指针即可，不再对区间的内容进行传递，避免内存占用过大或者时间占用过多

分治算法的边界

• 一个函数不可能无止尽地递归下去，这样肯定会超时和爆栈，将一个问题分成几个子问题，再将子问题继续分成子子问题，如果就像这样无止尽地循环下去，我们肯定无法得到最终的结果，因此，分治算法肯定会有一个最小的子问题，也就是分治算法的边界条件，这个边界条件对应的问题我们通常可以直接判定，这个问题通常只涉及到了一两个元素，我们直接进行处理然后返回结果即可，无需再进行拆分。
• 通过边界条件，我们可以确定分治算法的函数返回的到底是什么，并以此为基础分析最优解，来写整个函数。

分治算法的常见题型及讲解

归并排序及逆序对问题

归并排序

给$n$个数，将这些数从小到大排列

思路：

我们先将这些数平分成左半部分和右半部分，分别先对左半部分和右半部分从小到大排序，然后我们再来处理当前这些数：

因为左半部分与右半部分都已经排好序，假设当前这些数的左端点指针为$left$，右端点指针为$right$，存储这些数的数组为$a[]$，$mid=\frac{(left+right)}{2}$，也就是说，我们先分别对$a[left]到a[mid]$、$a[mid+1]到a[right]$从小到大排序，然后再对两边从小到大合并，合并的方法为：

• 设置两个指针$i$和$j$，其中指针$i$在这些数的左半部分移动，指针$j$在这些数的右半部分移动，很容易知道，如果$i<mid$，则$a[i]\le a[i+1]$；如果$j<right$，则$a[j]<a[j+1]$
• 设置一个数组$b[]$，用来存储重新排序后的$a[]$，处理完后再赋值回给$a[]$
• 如果$a[i]\le a[j]$，则将$a[i]$先赋值给$b[]$的最后一个位置，然后$i++$；如果$a[i]>a[i]$，则将$a[j]$先赋值给$b[]$的最后一个位置，然后$j++$。这里我们假设$b[]$的最后一个位置为$q$，则$q\in [left,right]$,前面的内容可以表示为：
  • 如果$a[i]\le a[j]$，则$b[q]=a[i],q++,i++$；如果$a[i]>a[j]$，则$b[q]=a[j],q++,j++$。
• 注意：如果$i>mid$，余下的数都在右半部分，则$b[q]=a[j],j++,q++$；如果$j>right$，余下的数都在左半部分，则$b[q]=a[i],i++,q++$

C++代码：

void ssort(int left, int right)
{
  if(left == right)
    return;
  int mid = (left + right) / 2;
  ssort(left, mid);
  ssort(mid + 1, right);
  int i = left, j = mid + 1;
  for(int q = left; q <= right; q ++)
  {
    if(j > right || a[i] <= a[j])
      b[q] = a[i++];
    else
      b[q] = a[j++];
  }
  for(int q = left; q <= right; q ++)
    a[q] = b[q];
  return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

逆序对问题

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
比如一个元素个数为4的数列，其元素为2，4，3，1，则(2,1)，(4,3)，(4,1)，(3,1)是逆序，逆序数是4
现在求给定数列的逆序数

思路：

对于这个问题，我们很容易想到$\Theta (n^2)$的算法，也就是枚举一个数后面的所有的数，记录比这个数小的数的个数。

但如果我们使用归并排序去处理，这道题的时间复杂度可以从$\Theta (n^2)$降低为$\Theta (nlo{g}_{2}n)$，

我们如何使用归并排序的方法去求逆序对的个数呢？

对于$a[left]$到$a[right]$，我们把它们分为$a[left]$到$a[mid]$、$a[mid+1]$到$a[right]$两个部分，其中，$mid=(left+right)÷2$，分别先对左半部分和右半部分从小到大排序，接下来再进行合并：

• 如果$b[q]=a[j]$，则对于$a[j]$而言，$a[mid+1]$到$a[j-1]$肯定都放在了$a[j]$之前，而$a[left]$到$a[mid]$本身就在$a[j]$的前面，如果$a[left]$到$a[mid]$都比$a[j]$小，则$q$应该等于$j$，如果$a[left]$到$a[mid]$中有比$a[mid]$小的，则$q<j$，$a[j]$对应的逆序对个数为$j-q$

C++代码：

int ssort(int left, int right)
{
  if(left == right)
    return 0;
  int mid = (left + right) / 2;
  int sum = 0;
  sum += ssort(left, mid);
  sum += ssort(mid + 1, right);
  int i = left, j = mid + 1;
  for(int q = left; q <= right; q ++)
  {
    if(j > right || a[i] <= a[j])
      b[q] = a[i++];
    else
      b[q] = a[j], sum += (q - j), j ++;
  }
  for(int q = left; q <= right; q ++)
    a[q] = b[q];
  return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

快速排序和第k小数

快速排序

给$n$个数，将这些数从小到大排列

思路：

如果我们使用归并排序，虽然其时间复杂度为最优，但其需要多开一个数组，比较消耗内存，空间复杂度较大，而快速排序则不需要多开一个数组，但快速排序的时间复杂度不稳定，最优时为$nlo{g}_{2}n$，最差时为$n^2$，最差的情况为：原本的数列按从大到小排序，而我们需要更改为从小到大排序，对于这种情况，有一种优化的方法：将数列打乱后进行快速排序。

快速排序的内容：

• 在$a[left]$到$a[right]$中选定一个基准，将比基准小的数都放到基准的左边，比基准大的数都放到基准的右边；然后将对基准左边的数进行相同处理，对基准右边的数进行相同处理。

假设我们选定的基准为$a[mid]$，$mid=\frac{left+right}{2}$，

我们如何将比$a[mid]$小的数放到$a[mid]$左边，将比$a[mid]$大的数放大$a[mid]$右边呢？

我们可以设置两个指针$i$与$j$，首先让$i=left$，$j=right$，然后$j$往左走，$i$往右走:

• $j$往左走找到第一个小于等于$a[mid]$的数
• $i$往右走找到第一个大于等于$a[mid]$的数
• 交换这两个数
• $i++$，$j--$

注意：需要保证$i\le j$

这么处理后，我们可能会把$a[mid]$的位置都换了，我们有两种处理方法：

• 第一种：记录变更后的$mid$，假设变更后的为$q$，也就是把$a[mid]$放到了$a[q]$，接下来，我们只需要对$a[left]$到$a[q-1]$、$a[q+1]$到$a[right]$分别进行相同处理即可
• 第二种：因为循环的条件为$i\le j$，则最终退出循环时，$i$与$j$的关系为$i=j+1$或者$i=j+2$：
  • 最后一次循环开始时，满足$i\le j$，如果循环之后$i$变为了$i^{\prime }$，循环之后$j$变为了$j^{\prime }$，$i$先动，易知$a[j+1]\ge a[mid]$，则$i^{\prime }\le j+1$，易知$a[i^{\prime }-1]\le a[mid]$，则$j^{\prime }\ge i^{\prime }-1$:
    • 如果$j^{\prime }=i^{\prime }-1$，退出循环
    • 如果$j^{\prime }\ge i^{\prime }$，交换$a[i^{\prime }]$与$a[j^{\prime }]$，然后$i^{\prime }++$，$j^{\prime }--$，然后退出循环，因为退出循环，则必定在交换之前满足$i^{\prime }=j^{\prime }-1$或者$i^{\prime }=j^{\prime }$，否则$i^{\prime }++,j^{\prime }--$后依旧会满足$i^{\prime }\le j^{\prime }$，因此，退出循环时，$i^{\prime }=j^{\prime }+1$或者$i^{\prime }=j^{\prime }+2$
  • 如果最终$i=j+1$，则数列可以分为$a[left]$到$a[j]$、$a[i]$到$a[right]$，我们分别对这两个区间进行相同处理即可
  • 如果最终$i=j+2$，则数列可以分为$a[left]$到$a[j]$、$a[i+1]$、$a[i]$到$a[right]$三个部分，而$a[i+1]$只有一个数，无需再处理，因此我们分别对$a[left]$到$a[j]$、$a[i]$到$a[right]$进行相同处理即可

C++代码：

void quick_sort(int left, int right)
{
  int i = left, j = right, mid = (left + right) / 2;
  int x = a[mid];
  while(i <= j)
  {
    while(a[i] < x) i ++;
    while(a[j] > x) j --;
    if(i <= j)
    {
      int b = a[i];
      a[i] = a[j], a[j] = b;
      i ++, j --;
    }
  }
  if(j > left) quick_sort(left, j);
  if(i < right) quick_sort(i, right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第k小数

给你一个长度为$n$的序列，求序列中第$k$小数的多少。

思路：

我们可以直接对这个序列进行从小到大的排序，时间复杂度为$\Theta (nlo{g}_{2}n)$，然后直接输出第$k$个数

当然，我们也可以修改一下快速排序的代码，使得可以更快地去找到这个数：

我们依旧是选择一个基准，如果然后将比基准小的数都放到基准左边，经比基准大的数都放大基准的右边，记录最后基准所处的位置，如果基准的位置大于$k$，则对基准左边的数进行相同处理（不处理基准右边的数）；如果基准的位置小于$k$，则对基准右边的数进行相同处理（不处理基准左边的数）；如果基准的位置等于$k$，则直接返回此数；

树的遍历

树的先序遍历

先遍历树的根节点，然后遍历树的左子树，最后遍历树的右子树，对于所有子树的处理方式相同，如果此节点为叶节点，则直接返回该节点

先序遍历的结果为：

树的中序遍历

先遍历树的左子树，然后遍历树的根节点，最后遍历树的右子树，对于所有子树的处理方式相同，如果此节点为叶节点，则直接返回该节点

中序遍历的结果为：

树的后序遍历

先遍历树的左子树，然后遍历树的右子树，最后遍历树的根节点，对于所有子树的处理方式相同，如果此节点为叶节点，则直接返回该节点

后续遍历的结果为：

给出二叉树的先序遍历和中序遍历，求后序遍历

首先，我们知道，先序遍历的最左边肯定是根节点，在中序遍历中找到这个根节点，则中序遍历中，这个根节点的左边肯定是左子树，这个根节点的右边肯定是右子树。则我们可以将中序遍历中根节点左边和右边的部分分别进行同样的处理：在先序遍历中找到根节点，然后继续在中序遍历中找到左子树和右子树，当最后只有一个字符时，就代表该节点为叶节点。

注意：不管是先序遍历、中序遍历还是后序遍历，左子树的所有节点在字符串中肯定都是连在一起的，中间不可能出现其他的节点，同样，右子树的所有节点在字符串中肯定也是连在一起的，中间不可能出现其他的节点。

假设一棵二叉树的先序遍历为$ABCDFE$，中序遍历为$BADFCE$

则：先序遍历确定$A$为根节点，从中序遍历，可以确定左子树为$B$，右子树为$DFCE$，因为左子树只有一个节点，因此$B$为叶节点，然后我们看右子树部分：先序遍历为$CDFE$，中序遍历为$DFCE$，根据先序遍历，确定根节点为$C$，中序遍历确定左子树为$DF$，右子树为$E$。然后我们看左子树比分：先序遍历为$DF$，中序遍历为$DF$，根据先序遍历，确定根节点为$D$，根据中序遍历，确定右子树为$F$，因此，这棵树为：

空的代表没有此节点

给出二叉树的中序遍历和后序遍历，求先序遍历

首先，我们知道，后序遍历的最右边肯定是根节点，在中序遍历中找到这个根节点，则中序遍历中，这个根节点的左边肯定是左子树，这个根节点的右边肯定是右子树。则我们可以将中序遍历中根节点左边和右边的部分分别进行同样的处理：在后续遍历中找到根节点，然后继续在中序遍历中找到左子树和右子树，当最后只有一个字符时，就代表该节点为叶节点。

给出二叉树的先序遍历和后续遍历，无法求出中序遍历

先序遍历的最左边肯定是根节点，后序遍历的最右边肯定是根节点，但我们无法从中区分出左子树与右子树，因此，给出二叉树的先序遍历和后序遍历，我们无法确定这颗二叉树，因此也就无法求出中序遍历。

限定条件下的先序遍历和后序遍历，求中序遍历

给定先序遍历和后序遍历，限定：若某节点只有一个子节点，则此处将其看做左子节点。

首先，我们知道，先序遍历的最左边肯定是根节点，先序遍历的第二个字符肯定是根节点的左子树的根节点；后序遍历的最右边肯定是根节点，根据根节点的左子树的根节点，在后序遍历中找到这个节点，然后这个节点的左边肯定都是左子树的部分，这个节点的右边到根节点的左边肯定是右子树部分，依次类推。

表达式求值

假设一个表达式中有$+,-,\times ,÷,$次方和阶乘运算，其中，阶乘的优先级最高，其次是次方，然后是乘除，最后是加减。括号( )可以更改优先级，优先算优先级高的，在优先级相同时，从左到右计算。给出一个表达式，求出其值。

思路：

我们在这个表达式中找到所有运算符最后出现的位置，如果没有出现该运算符，则记为-1，然后看出现的优先级最低的字符串，假设其最后位置为$k$，则我们计算$[left,k-1]$的值，计算$[k+1,right]$的值，最后面将这两个值的运算结果（取决于这个运算符）返回。也就是说，我们从最后计算的开始处理，如果优先级相同，则我们先从最后一个运算符开始，然后计算这个运算符左边的部分和右边部分的值，最后再处理这两个值的运算。当然，如果这个运算符号为$!$，也就是阶乘，我们只需要计算这个运算符左边的部分即可，最后返回左边数值的阶乘结果。

注意：因为括号可以更改运算优先级，括号内的部分我们则直接忽略，不统计其内的运算符号，记录括号外部的运算符号最后出现的位置，如果分治后该表达式被括号包围，那么就代表我们已经处理到括号内部的表达式了，去除该表达式最左边和最右边的两个字符，也就是(和)，然后继续正常处理即可。

棋盘覆盖问题

有一个$2^k\times 2^k$的方格棋盘，恰有一个方格是黑色的，其他为白色。你的任务是用包含3个方格的$L$型牌覆盖所有的白色方格。黑色方格不能被覆盖，且任意一个白色方格不能同时被两个或更多牌覆盖。如图所示为$L$型牌的四种旋转方式：

思路：

本题的棋盘是$2^k\times 2^k$的，很容易想到分治：吧棋盘切为4块，则每一块都是$2^{k-1}\times 2^{k-1}$的。有黑格的那一块可以递归解决，但其他三块没有黑格子，应该怎么办呢？可以构造出一个黑格子，如图，递归边界也不难得出：$k=1$时一块牌就够了。————《算法竞赛入门经典》

循环日程表问题

$n=2^k$个运动员进行网球循环赛，需要设计比赛日程表。每个选手必须与其他$n-1$个选手各赛一次；每个选手一天只能赛一次；循环赛一共进行$n-1$天。按此要求设计一张比赛日程表，该表有$n$行和$n-1$列，第$i$行$j$列为第$i$个选手第$j$填遇到的选手。

思路：

本题的方法有很多，递归分治是其中一种比较容易理解的方法。

我们可以将这个日程表平分为四份，左上半部分可以先让前$2^{k-1}$相互比赛，左下半部分可以先让后$2^{k-1}$相互比赛，其中左上半部分和左下半部分可以理解为它们是对称的，只是比赛人的编号不一样，因为左下半部分为$2^{k-1}+1$到$2^k$编号的人相互比赛，左上半部分为1到$2^{k-1}相互比赛$

因此，左下半部分可以为左上半部分的编号加上$2^{k-1}得到$。

因为左上半部分和左下半部分都保证了同一个编号在同一行、同一列中都只出现了一次，而右上半部分为编号$1到2^{k-1}和2^{k-1}+1到2^k$相互比赛，左下半部分仅有$2^{k-1}+1到2^k$，右上半部分也需要填入$2^{k-1}+1到2^k$的部分，因此右上半部分可以直接复制左下半部分，同理，右下半部分可以直接复制左上半部分。

因此，我们只需要处理左上半部分，剩下的部分都可以通过左上半部分得到，而左上半部分继续分治递归即可。

注意：第一列为队伍名，后面的第$k$列为该队伍第$k-1$天与之比赛的队伍名

巨人与鬼

在平面上有$n$个巨人和$n$个鬼，没有三者在同一条直线上。每个巨人需要选择一个不同的鬼，向其发送质子流消灭它。质子流由巨人发射，沿直线进行，遇到鬼后消失。由于质子流交叉是很危险的，所有质子流经过的线段不能有交点。请设计一种给巨人和鬼配对的方案。

思路：

由于只需要一种配对方案，从直观上来说本题是一定有解的。由于每一个巨人和鬼都需要找一个目标，不妨先给“最特殊”的巨人或鬼寻找“搭档”。
考虑$y$坐标最小的点（即最低点）。如果有多个这样的点，考虑最左边的点（即其中最左边的点），则所有点的极角在范围$[0,\pi )$内。不妨设它是一个巨人，然后把所有其他点按照极角从小到大的顺序排序后依次检查。
情况一：第一个点是鬼，那么配对完成，剩下的巨人和鬼仍然是一样多，而且不会和这一条线段交叉。
情况二：第一个点是巨人，那么继续检查，知道已检查的点中鬼和巨人一样多为止。找到了这个“鬼和巨人”配对区间后，只需要把此区间内的点配对，再把区域外的点配对即可。这个配对过程是递归的，好比棋盘覆盖中一样，会不会找不到这样的配对区间呢？不会的。因为检查完第一个点后鬼少一个，而检查完最后一个点时鬼多一个，而巨人和鬼的数量差每次只能改变1，因此“从少到多”的过程中一定会有“一样多”的时候。————《算法竞赛入门经典》

汉诺塔问题

将$n$个圆盘从第一根柱子上移到第三根柱子上，相当于先将前$n-1$个圆盘从第一根柱子移到第二根柱子上，然后将第$n$个圆盘从第一根柱子移到第三根柱子上，再将前$n-1$个圆盘从第二根柱子移到第三根柱子上；将前$n-1$根柱子从第$A$根柱子上移动到第$B$根柱子上可以使用同样的方法，使用分治递归实现。

汉诺塔问题可以详见：
汉诺塔问题

平面最近点问题

在平面直角坐标上给定n个点的坐标，找到距离最短的两个点，输出这两个点的距离。

思路：

我们很容易想到$\Theta (n^2)$的算法：枚举所有的两个点组合，找到其中距离最短的那一组。

其实这题使用分治算法能够更快地解出题目：

先将这些点按照$x$坐标从小到大排序，排序后为$a_1,a_2,a_3,...,a_n$，接下来使用分治思路：

• 将这些点分为左半部分和右半部分（这些点已经按照$x$从小到大排好序，我们将这些点分为平分为两份，左半部分的点的$x$坐标均小于右半部分的点）
• 求左半部分的点之间的最短距离$l_1$
• 求右半部分的点之间的最短距离$l_2$
• 设$d=min(l_1,l_2)$
• 求左半部分与右半部分各选一个点之间的最短距离：
  • 我们先对这些点进行一下筛选：首先，在$a[left]到a[right]$中选取左半部分中与$a_{mid}横向距离$小于等于$d$的，然后选取右半部分中与$a_{mid}$横向距离小于等于$d$的，假设选出来的这些点存储在$b_1,b_2,...,b_m$中
  • 将选出来的这些点按照纵坐标从大到小排序，当我们处理$b_i$时，只需要管$b_i$后面的坐标，也就是纵坐标比$b_i$的纵坐标要小的点，而$b_i$前面的点已经处理过了，无需再重复处理。我们在看$b_i$后面的点时，假设我们看$b_{i+p}这个点$，如果其与$b_i$的纵坐标之差的绝对值（也就是纵向距离）大于等于$d$，则我们可以直接退出这一次循环，不再处理$b_i$，继续循环$b_{i+1}，$这样可以减少循环次数；如果$b_{i+p}与b_i$的纵向距离小于$d$，则我们求出$b_i$与$b_{i+p}的$距离$l$，然后$d=min(d,l)$

我们处理$b_i$时，$b_i$内部的循环不会超过7次，也就是说在$b_i$之后至多有7个点的与$b_i$的纵向距离小于$d$:在选定的$a_{mid}的$左边，也就是与$a_{mid}横向距离$小于d的那一部分中，我们画一个边长为$d$的正方形，这个正方形的左右边界就是选定左半部分的左右边界，因为左半部分所有点之间的最短距离肯定$\ge d$，因此，在这个正方形中，至多可以放入四个点，同理，在选定的右半部分同样如此，假设$a_i$就是处于正方形的左上角，则这样最多有7个点与$a_i$的纵向距离$\le d$————由此可以推出，这个算法的时间复杂度为$\Theta (nlo{g}_{2}n)$