分治法的基本思想

总体思想

定义：讲一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

1. 将待求解的较大规模问题分割成k个更小规模的问题
2. 对这k个子问题分别求解
3. 如果子问题的规模仍然不够小，再划分为k个子问题，如此递归，直到问题规模足够小，可以直接求出解为止

分治法的适用条件

分治法所能解决的问题一般具有以下几个特征：

1. 该问题的规模缩小到一定的程度就可以容易解决
2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
3. 利用该问题分解出的子问题的解可以合并为该问题的解（如果只具备上述两个条件，但是这个条件不满足的话，则考虑使用贪心算法或动态规划）

4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题（重复地解公共子问题用动态规划比较好）

   注：建议使用分治法时要将子问题的规模划分的较为一致，即平衡子问题

分治法的复杂度分析

概述：

1. 一个分治法将规模为n的问题分成a个规模为n/b的子问题去解
2. 当 n 0 n_{0} n0​=1,且可以直接求解时，时间单位为1

3. 设将原问题分解为a个子问题以及用merge将a个子问题的姐合并为原问题的解需要用f(n)个单位时间

   用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间

T ⁡ ( n ) = { O ( 1 ) n = 1 aT ⁡ ( n / b ) + f ( n ) n > 1 \operatorname{T}(\mathrm{n})=\left\{\begin{array}{cl} O(1) & \mathrm{n}=1 \\ \operatorname{aT}(\mathrm{n}/b)+\mathrm{f(n)} & \mathrm{n}>1 \end{array}\right. T(n)={O(1)aT(n/b)+f(n)​n=1n>1​

（PS：这个求导公式太复杂了，计算麻烦，直接给出最终的情况）

分治法算法复杂度分析的情况

T ( n ) = { O ( n ) a < b O ( n l o g b n ) a = b O ( n l o g b a ) a > b T(n)=\left\{ \begin{aligned} O(n) & & a < b\\ O(nlog_{b}n) & & a = b \\ O(n^{log_{b}a}) & & a > b \end{aligned} \right. T(n)=⎩⎪⎨⎪⎧​O(n)O(nlogb​n)O(nlogb​a)​​a<ba=ba>b​

分治法之二分查找

二分查找要求被查找数组必须是有序的，首先从中点位置开始查找mid=(high+low)/2，然后和key进行比较

（1）若key==a[mid]，则查找成功并返回该元素下标

（2）若key<a[mid]，则查找左子表a[low……mid-1]

（3）若key>a[mid]，则查找右子表a[mid+1……high]

注：记得往子表进行查找时，mid一定要+1/-1，因为mid已经与key进行对比了，所以不必要再次算入

二分查找的时间复杂度很好计算O(logn)

（PS：我觉得二分查找这个东西应该挺好理解，而且也很简单实现，就不在过多描述了）