递归树

一：递归树与时间复杂度分析

1，递归思想就是将大问题分解为小问题来求解，然后在将小问题分解为小小问题，将问题一层一层地分解，直到问题的数据规模被分解得足够小，不要继递归分解为止。

2，用递归树来求解归并排序的时间复杂度

①：每次分解是一分为二，所以代价很低，将时间上的消耗记作常量1。
②：归并算法中比较耗时的归并操作，也就是把两个子数组合并为大数组
③：每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关，将每层归并操作消耗的时间记作n。
④：我们只需要知道这颗树的高度h,用高度乘以每层的时间消耗n,就可以得到总的时间复杂度O(n*h)。
⑤：从归并排序的原理和递归树，可知归并排序递归树是一颗满二叉树，满二叉树的高度大约为log2n，所以归并排序递归实现的时间复杂度就是O(nlogn)。

二：分析快速排序的时间复杂度

①：快速排序在最好情况下，每次分区都能一份为二，这个时候用递归公式T(n)=2T(n/2)+n，可以推导出时间复杂度是O(nlogn)。
②：但并不是总能非常平均的分区，所以通过公式推导时间复杂度会非常复杂。
③：快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是n。只要求出递归树的高度h，这个快排过程遍历的数据个数就是hn，即时间复杂度就是O(hn)。
④：因为每次分区并不是均匀地一分为二，所以递归树并不是满二叉树。
⑤：因为快速排序结束的条件是待排序的小区间，大小为1，即叶子节点里的数据规模是1。
⑥：从根节点n到叶子节点1，递归树中最短的一个路径每次都乘以1/10，最长的一个路径每次都乘以9/10。
⑦：通过计算，从根节点到叶子点最短路径是log10n,最长的路径是log10/9 n。

⑧：遍历数据的个数总和就介于nlog10n和nlog10/9 n之间。根据复杂度O表示法规则，当分区大小比例是1:9时，快速排序的时间复杂度仍然是O(nlogn)。

三：斐波那契数列的时间复杂度

①：f(n)分解为f(n-1)和f(n-2)，每次数据规模都是-1或-2，叶子节点的数据规模是1或2。所以从根节点走到叶子节点，每条路径是长短不一的。
②：如果每次都是-1，那最长路径大约就是n；如果每次都是-2，那最短路径大约就是n/2。
③：第k层的时间消耗是2(^{k-1)，总时间消耗之和是2}n -1

四：分析全排列的时间复杂度

n + n(n-1) + n(n-1)(n-2) +... + n(n-1)(n-2)...21