递归树分析归并排序算法复杂度
之前学算法分析的时候只知道通过数语句来计算算法的复杂度,而对于递归算法没有很好的方法;
由于递归算法通常采用分治思路,每递归一次,子问题在增多,但是子问题的规模在减少,所以如何去计算这种递归类算法的复杂度呢?
斯坦福的教授提供了一种使用 递归树 的方法。
归并的复杂度
这里我们采用经典的归并排序算法作为一个例子,使用递归树来分析它的复杂度。
我们知道,归并排序算法主要分为三个步骤:
- 递归左半部分
- 递归右半部份
- 将排好序的左半边和右半边合并
对于归并(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++
首先在循环部分,循环的每一次执行了 次操作,所以一共需要 次操作;
然后初始化 i
和 j
需要两次操作;
所以,归并部分一共执行 次操作,由于 ,所以:
粗糙一点,我们可以使用 作为归并部分的复杂度。
递归树和归并排序的复杂度
对于我们的递归程序,我们采用递归树来分析它的复杂度:
其中,横条表示的是 输入数据的长度,根节点的输入规模为 ;
每进行一次递归,树就向下深入一层;
那么,根据二叉树结论,树的总层数为 ;
对于第 层,拥有 个节点,同时每个节点的输入规模为
所以,对于第 层,其执行的操作数为:
而二叉树一共有 层,所以,归并排序的总复杂度是:
所以,我们就得到了归并排序的总复杂度
总结
这里来总结一下使用递归树进行算法分析的步骤:
- 计算递归的每一步中的复杂度
- 按照递归的分裂程度,画出不同的递归树
- 分析 每一层 的时间复杂度,重点关注节点数量和该层每节点的输入规模
- 每一层的复杂度乘以层数,就是递归算法的总复杂度