递归树

比如一棵斐波那契数列的递归树，节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。

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