递归树分析归并排序算法复杂度

发表于 2018-02-19 更新于 2018-02-20 分类于 Algorithm 阅读次数：

本文字数： 983 阅读时长 ≈ 2 分钟

之前学算法分析的时候只知道通过数语句来计算算法的复杂度，而对于递归算法没有很好的方法；

由于递归算法通常采用分治思路，每递归一次，子问题在增多，但是子问题的规模在减少，所以如何去计算这种递归类算法的复杂度呢？
斯坦福的教授提供了一种使用 递归树 的方法。

归并的复杂度

这里我们采用经典的归并排序算法作为一个例子，使用递归树来分析它的复杂度。

我们知道，归并排序算法主要分为三个步骤：

对于归并(merge)部分，我们可以很清楚地计算出其复杂度：

for k from 0 to N-1:
    if A[i] < B[j]:
        C[k] = A[i]
        i++
    else if B[j] < A[i]:
        C[k] = B[j]
        j++

首先在循环部分，循环的每一次执行了 $4$ 次操作，所以一共需要 $4N$ 次操作；

然后初始化 i 和 j 需要两次操作；

所以，归并部分一共执行 $4N + 2$ 次操作，由于 $N \ge 1$ ，所以：

4N + 2 \le 6N

粗糙一点，我们可以使用 $6N$ 作为归并部分的复杂度。

对于我们的递归程序，我们采用递归树来分析它的复杂度：

其中，横条表示的是 输入数据的长度，根节点的输入规模为 $N$ ；

每进行一次递归，树就向下深入一层；

那么，根据二叉树结论，树的总层数为 $\log{N} + 1$ ；

对于第 $j$ 层，拥有 $2^j$ 个节点，同时每个节点的输入规模为 $N / {2^j}$

所以，对于第 $j$ 层，其执行的操作数为：

2^j \times 6(N/2^j) = 6N

而二叉树一共有 $\log{N}$ 层，所以，归并排序的总复杂度是：

(\log{N} + 1) \times 6N = 6N\log{N} + 6N

所以，我们就得到了归并排序的总复杂度 $O(N\log{N})$

这里来总结一下使用递归树进行算法分析的步骤：