0%

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

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

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

归并的复杂度

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

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

  1. 递归左半部分
  2. 递归右半部份
  3. 将排好序的左半边和右半边合并

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

1
2
3
4
5
6
7
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++

首先在循环部分,循环的每一次执行了 44 次操作,所以一共需要 4N4N 次操作;

然后初始化 ij 需要两次操作;

所以,归并部分一共执行 4N+24N + 2 次操作,由于 N1N \ge 1,所以:

4N+26N4N + 2 \le 6N

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

递归树和归并排序的复杂度

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

其中,横条表示的是 输入数据的长度,根节点的输入规模为 NN

每进行一次递归,树就向下深入一层;

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

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

所以,对于第 jj 层,其执行的操作数为:

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

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

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

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

总结

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

  1. 计算递归的每一步中的复杂度
  2. 按照递归的分裂程度,画出不同的递归树
  3. 分析 每一层 的时间复杂度,重点关注节点数量该层每节点的输入规模
  4. 每一层的复杂度乘以层数,就是递归算法的总复杂度