分治法

分治思想

并不仅仅是一种算法，更是一种设计算法的思想

基本思想

1. Divide ：把问题分解
2. Conquer ：递归的解决每一个分解出来的问题
3. Merge ：合并解决的问题

学而不思则罔

分析几种使用分治思想的算法，希望从中学到如何去拆解问题，治理问题

归并排序

分治思想分析

1. 分解：将待排序数组一分为二

   降低问题规模，比如我们要从排序n个数，我们可以把这个问题分解成两个问题（即排序n/2个数），此时我们的问题规模直接降低了一半，我们还可以递归的将问题继续分解，问题规模会变成n/4…n/8…

2. 治理问题：递归的对每个子数组进行排序

   这一步是会递归的执行（1，2，3步骤），因为我们要把问题分割的尽可能小，小到哪种程度呢，当然是只有一个数的情况，那样就不用排序了，因为只有一个数

3. 合并问题：很明显合并已经排序好的两个数组，可以在线性时间内完成，这里是$O(n)$
   我们解决了分解之后的问题，这时候需要按照一定的规则把分解之后的问题，组合起来，这里就是把已经排序好的数合并起来

时间复杂度

1. 递归表达式

   $T(N)=2T(\frac{N}{2})+N$

   其中，$n$表示问题规模，$T(N)$表示解决问题$n$需要的时间，$2T(N/2)$表示需要把一个规模为$N$的问题分解成两个$N/2$规模的问题，最后的$N$是指额外的工作，这里指的是合并子问题需要花费的时间

2. 可视化的方法搞清楚时间复杂度

• 首先，我们把N递归分解，能分解多少次？(分解是没有复杂度的，因为分解并没有实际的计算)
• 其次，我们需要计算多少次

观察上图，可知最多会有$lo{g}^n$层，每层需要$n$次计算（这里的计算，是把排序好的数据，合并到一起）

3. 数学方法搞清楚时间复杂度

首先根据递归式我们可以得到下面的等式 ：

$\{\begin{array}{l}T(1)=1\\ T(N)=2T(N/2)+N\end{array}$

我们让等号两边除以$N$得到:

​ $\frac{T(N)}{N}=\frac{T(N/2)}{N/2}+1$

​ $\frac{T(N/2)}{N/2}=\frac{T(N/4)}{N/4}+1$

​ $\frac{T(N/4)}{N/4}=\frac{T(N/8)}{N/8}+1$
…
​ $\frac{T(2)}{2}=\frac{T(1)}{1}+1$

将所有这些方程相加得到：

​ $\frac{T(N)}{N}=\frac{T(1)}{1}+logN$

所以就有：

​ $T(N)=N+N\ast logN$

当然，也有很多其它排序方法都能达到这个速度，甚至一些情况下，有$O(n)$复杂度的排序算法，但是归并排序，相对来说比较稳定，通用

排序算法时间复杂度比较

二分查找

分治思想分析

有序的数$[n_1,n_2,n_3....n_i]$中查找目标数$x$

查找目标数：$x$

1. 分解：$x$ 和 中间数比较
2. 治理：如果$x$和中间数不同，那么就根据大小关系，让子数组进行递归（这里会根据条件，递归执行1，2，3步骤）
3. 合并：这里不需要额外计算，因为找到这个数（或者证明这个数不存在）就可以了

时间复杂度

$T(n)=T(n/2)+\theta (1)$

计算 $n^m$

分治思想分析

1. 分解：将计算 $n^m$ 分解为计算 $n^{m/2}$
   这里假设m是偶数，如果m是奇数，只需要先设置 $m=m-1$，算法执行结束后乘以 $n$，问题规模同样降低了一半

2. 治理：递归的将问题分解，最终最小的问题将是 $n^1$

3. 合并：将得到的结果自身相乘

   这里的操作就是将两个数相乘，所以这里的时间复杂度为 $\theta (1)$

时间复杂度

$T(n)=T(n/2)+\theta (1)$

实践

LeetCode 寻找两个有序数组的中位数

我的个人博客,有空来坐坐