分治法

分治思想

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

基本思想

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

学而不思则罔

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

归并排序

分治思想分析

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

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

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

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

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

时间复杂度

1. 递归表达式

   

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

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

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

graph TD;
    N-->N2_1;
    N-->N2_2;
    N2_1-->N4_1;
    N2_1-->N4_2;
    N2_2-->N4_3;
    N2_2-->N4_4;

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

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

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

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

​

​
......
​

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

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

排序算法时间复杂度比较

二分查找

分治思想分析

有序的数中查找目标数

查找目标数：

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

时间复杂度

计算

分治思想分析

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

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

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

   这里的操作就是将两个数相乘，所以这里的时间复杂度为

时间复杂度

实践

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

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