1-分治法

分治法适用范围

• $n$ 取值很大，直接求解十分困难；
• 将 $n$ 个输入拆分成 $k$ 个不同的子集，可以得到 $k$ 个可求解的子问题；
• 在找出子问题的解后，能够通过某种方法将它们合并为整体问题的解。

分治法求解思路

整体思想： 将总体问题 分而治之，十分适合使用递归的方法进行求解

• 分：子问题与原问题有相同特征，但规模更小；
• 治：反复利用分治策略，直到可以直接求解子问题；
• 合：将子问题的解组合成原问题的解。

分治法的时间复杂度

分治法的时间复杂度直接计算较为复杂，通常利用主定理进行计算。

记 $\alpha$ 为子问题个数，$b$ 为问题的缩小规模，$f(n)$ 为分解与合并的代价，分治法的时间复杂度可以表示为：

$$T(n)=\alpha T(\frac{n}{b})+f(n)$$

其中，根据 $f(n)$ 的不同数量级，可以认为 $T(n)$ 收敛于不同数量级的复杂度：

$$T(n)=\{\begin{array}{ll}\Theta (n^{{\log }_{b}a}),& f(n)=O(n^{{\log }_{b}a-ϵ})\\ \Theta (n^{lo{g}_{b}a}\log n),& f(n)=O(n^{{\log }_{b}a})\\ \Theta (f(n)),& f(n)=O(n^{{\log }_{b}a+ϵ})\end{array}$$

举例

二分查找

问题描述

已知一个非降序 $a_1,a_2,\cdots ,a_n$，判断元素 $x$ 是否位于其中。若是，则返回对应的位置。

分治法分析

1. 分： 取一个下标 $k$，记 $I_1=(a_1,\cdots ,c_{k-1}),I_2=(a_k),I_3=(a_{k+1},\cdots ,c_n)$；
2. 治：
   • 若 $x=a_k$，则问题解决，位置为 $k$；
   • 若 $x<a_k$，则在 $I_1$ 中解决；
   • 若 $x>a_k$，则在 $I_3$ 中解决
3. 合： 子问题的解就是全局问题的解

时间复杂度分析

根据主定理，$T(n)=1\cdot T(\frac{n}{2})+O(1)$，其中，$f(n)=O(1)=O(n^{{\log }_{2}1})$，即 $T(n)=\Theta (n^{{\log }_{2}1}\cdot \log n=\Theta (\log n)$