分治 • CoderXL's Blog

分治是一种基本却又高深的算法思想。

运用分治，可以将 $O(n^2)$ 的排序优化到 $O(n\log n)$ ；可以将 $O(n^2)$ 的多项式乘法优化到 $O(n\log n)$ ；可以将 $O(n^2)$ 的树上路径问题优化到 $O(n\log n)$ . 更多的分治算法还有分治求平面最近点对 ↗，整体二分等等。

可以发现，分治的复杂度似乎总是涉及 $\log$ ，这和分治的底层逻辑密切相关。

注：分治的复杂度（主定理）请见计算理论#主定理 (Master Theorem) ↗.

思想#

分治基于这样的发问：

大问题能否被拆分成几个小问题
小问题的答案能否很方便地合并成大问题的答案

以排序为例，如果要将 $n$ 个数排序，那么可以考虑从前往后依次排序：

每次开头的 $k$ 个数已经有序，然后再向其中加入第 $k+1$ 个数。这就是插入/选择/冒泡排序的做法，每次加入一个数的复杂度是 $O(n)$ 的，整体是 $O(n^2)$ 的。

但是，如果我们先把序列平均分成前后两段，然后将两段分别排序，再合并两段。这个合并的过程仍然是 $O(n)$ 的，和冒泡排序中加入一个数的复杂度是一样的。但是由于此处是两段合并成一段，而不是将一个数加入一段数，因此每次排好序的序列长度能够成倍增加而不是线性增加。从这就导致我们「合并」操作的次数相对于「加入」操作的次数是 $\log$ 级别的，因此可以有效提升运行速度。这就是归并排序。

block-beta
columns 1
  block:L1
    A["8n"]
  end
  block:L2
    B[" "]
    C["4n"]
  end
  block:L3
    D[" "]
    E[" "]
    F[" "]
    G["2n"]
  end
  block:L4
    H[" "]
    I[" "]
    J[" "]
    K[" "]
    L[" "]
    M[" "]
    N[" "]
    O["n"]
  end

合并操作的“层高”是 $O(\log n)$ 的

实际上，冒泡和选择排序也可以被视为分治，不过它们的子问题划分非常不均匀，导致效率低下。

因此分治的关键，是检查长度为 $n$ 的「合并」操作的复杂度增长速度，是否显著低于单次操作的线性累加。如果是，那么先划分再合并就比依次进行单次操作更划算。

分治通常采用「自顶向下」的方式进行，借助函数的递归调用，先拆分成子问题，送入子函数求解，再将结果合并后返回。

应用#

关于分治在排序中的应用，另见排序 ↗；

关于分治加速多项式乘法的算法，另见 FFT ↗；

关于分治的大量习题，可见【每日一题】第一周 ↗。