递归树
比如一棵斐波那契数列的递归树,节点里的数字表示数据的规模,一个节点的求解可以分解为左右子节点两个问题的求解。
如何用递归树来求解时间复杂度
比如归并排序算法,我们把它画成递归树,就是下面这个样子:因为每次操作都是一分为二,所以代价很低,我们把时间上的消耗记作常量1。
归并算法中比较耗时的是归并操作,也就是把两个子数组合并为大数组。从图中可以看出,每一层归并操作消耗的时间总和是一样的,跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记作n。
现在,只需要知道树的高度h,用高度h乘以每一层的时间消耗n,就可以得到总的时间复杂度O(n*h)。又因为归并排序递归树是一棵满二叉树,满二叉树的高度大约是log以2为底n的对数,所以归并排序递归的时间复杂度就是O(nlogn)。