5. 分治算法 Divide and Conquer

分治思想

1. 将一个输入变成多个 sub-inputs
2. 将一个 subinput 通过递归找到子解决方法
3. 结合 (combine, or conquer) 子解决方法得到最终解决方法

归并排序

1. 将一个线性数组分割成两个等长的数组，长度 n/2
2. 对左右子数组分别执行归并排序（递归）复杂度
3. 将左右数组进行合并， 复杂度 $O(n)$

递归部分复杂度分析

首先我们明确这是一个类似二叉树的结构，所以，从层数上来讲，一共有 $\log_2 n$ 层，每一层的复杂度是 $O(n)$ (每一层都有合并)，所以递归部分的复杂度是 $O(n \log n)$

注意区分一般的二叉遍历

比如对分查找，我们想找到有序数组中最靠近 k 的位置，那么用对分查找，相比归并排序少了一个合并 (O(n)) 的步骤，时间复杂度是 $O(\log n)$
又或者是将一个数不断的用 $\lfloor x/2\rfloor$ 和 $x - \lfloor x / 2\rfloor$ 来进行二分，虽然看似是会遍历每一个 1，但是由于层数是 $O(\log n)$, 每一层里面做的都常数操作