分治法

2019-09-29 本文已影响0人躺在家里干活

分治思想

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

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

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

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

这一步是会递归的执行（1，2，3步骤），因为我们要把问题分割的尽可能小，小到哪种程度呢，当然是只有一个数的情况，那样就不用排序了，因为只有一个数
合并问题：很明显合并已经排序好的两个数组，可以在线性时间内完成，这里是 $O(n)$
我们解决了分解之后的问题，这时候需要按照一定的规则把分解之后的问题，组合起来，这里就是把已经排序好的数合并起来

递归表达式

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

其中， $n$ 表示问题规模， $T(N)$ 表示解决问题 $n$ 需要的时间， $2T(N/2)$ 表示需要把一个规模为 $N$ 的问题分解成两个 $N/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;

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

首先根据递归式我们可以得到下面的等式：
$\begin{cases} T(1) = 1 \\ T(N) = 2T(N/2) + N \end{cases}$
我们让等号两边除以 $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 * logN$

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

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

查找目标数： $x$

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

分解：将计算 $n^m$ 分解为计算 $n^{m/2}$
这里假设m是偶数，如果m是奇数，只需要先设置 $m = m -1$ ，算法执行结束后乘以 $n$ ，问题规模同样降低了一半
治理：递归的将问题分解，最终最小的问题将是 $n^1$
合并：将得到的结果自身相乘

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