分治法算法复杂度

分治法是一种常用的算法设计技巧,二分法就是其最常见的特例。所谓分治,分而治之也:

  • 分(divide):递归解决较小的问题
  • 治(conquer):从子问题的解构建原问题的解

一般来说,至少含有两个递归的程序才叫做分治法,只有一个递归的程序是不算的。下面来总结下分治法的算法复杂度问题,摘自《数据结构与算法分析——C语言描述》一书。

假设每次递归均可把原问题分解为$b$个规模一样的子问题,并需要求解其中的$a$个问题,将这$b$个子问题的解合并起来所需的算法复杂度为$O(N^k)$,即:

$$T(N)=aT(N/b)+\Theta (N^k)$$

此方程的解为:
$$T(N)=
\begin{cases}
O(N^{\log_b a}) & a>b^k\\
O(N^k \log N) & a=b^k\\
O(N^k) & a<b^k
\end{cases}$$

其中$a \geqslant 1, b > 1$

这个公式的实质是分和治的过程在争夺主导地位。大部分情况下$a=b$,此时上式可以进一步简化:
$$T(N)=
\begin{cases}
O(N^k) & k>1\\
O(N \log N) & k=1\\
O(N) & k<1
\end{cases}$$

一般也不存在 $k < 1$ 的情况,故我们可以得到一个最常用的结论:
若合并复杂度为 $O(N)$, 则整个分治法的复杂度为 $O(N \log N)$ ; 若合并复杂度为 $O(N^k), k>1$ , 则整个分治法的复杂度就是合并复杂度。且无论将问题分为几个子问题求解,其算法复杂度相同。