归并排序的递推公式是：

merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
终止条件：
p >= r 不用再继续分解

我们假设对n个元素排序的时间是T(n)，那分解成两个子数组排序的时间是$T(dfrac{n}{2})$

T(n)=2*T(n/2)+n
     =2*(2*T(n/4)+n/2)+n=4*T(n/4)+2n
     =4*(2*T(n/8)+n/4)+2n=8*T(n/8)+3n
     =8*(2*T(n/16)+n/8)+3n=16*T(n/16)+4n
     ...
     =2^k*T(n/2^k)+k*n

当$n/2^k=1$

递归的思想就是将大问题分解为小问题来求解。然后再将小问题分解成小小问题。这样一层层分解直到问题不能再分解。如果我们把这一层层的分解过程画成图，其实就是一棵树。我们把它叫做递归树。
参看下图，括号中的数字表示问题的规模。

归并排序比较耗时的操作是合并，也就是将两个小数组合并成一个大数组。其他操作的代价很低，可以记为常数L。
从图中看出每一层的耗时是相同的，都为n。现在我们只要知道这棵树的高度h，就可以得到总的时间复杂度O(h*n)。
从图中能看到这是一颗满二叉树。满二叉树的高度大约是$log_2n$

快排的递推公式：quick_sort(p…q) = quick_sort(p,i-1)+ quick_sort(i+1,q)
退出条件：p>=q
快排最好的情况是每次都能将数组一分为二。这时候用递推公式T(n)=2T(n/2)+n，就能得到时间复杂度O(nlogn)。
但是不可能每次都是理想情况。我们假设平均情况下每次分区，两个分区的比例是1:k。当k=9的时候，公式变为这样：
$T(n)=T(dfrac{9n}{10})+T(dfrac{n}{10})+n$

我们看到每一层因为有选择交换操作，且最多n次。所以每一层的操作代价是相同的：n。
递归树的路径长度却是不一样的。快排结束的条件是待排序的区间大小为1，也就是说叶子节点的数据规模是1。从节点n到叶子节点1，递归树中的最长路径是每次乘以$dfrac{1}{10}$

将k=99，999…替换之后结论相同。

上面的两个例子每层的操作数相同，都是n。这次需要具体分析每层的操作数。
菲波那切数列的实现代码：

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

把递归代码画成递归树如下。

f(n)分解为f(n-1)和f(n-2)，每次-1，或者-2。叶子节点的数据规模是1或者2。那最长路径大概就是n，最短路径大概是$dfrac{n}{2}$

每次分解之后的合并操作只是一次加法，算一个时间1。第一层是f(n-1)+f(n-2)，1次运算；第二层是f(n-2)+f(n-3)，f(n-3)+f(n-4)是两次运算…依次类推，第k层的总耗时是$2^{k-1}$。算法总耗时是每层耗时相加。

如果路径长度都为n，那么总耗时是：$2^n-1$

如果路径长度都为$dfrac{n}{2}$

所以算法的时间复杂度在$2^{dfrac{n}{2}}-1$

心得：时间复杂度是可以估算的，不用非常准确。只要数量级保证正确即可。

1 递归公式是

假设数组里的内容是1,2,3.....n
f(n)={最后一位是1,f(n-1)}+{最后一位是2,f(n-1)}+...+{最后一位是n,f(n-1)}

接着画出递归树。

2 对于问题f(n)，在得到子问题f(n-1)的结果之后需要把结果相加，有n次相加，所以第一层的操作数是n。
对于问题f(n-1)，首先会有n个f(n-1)的问题需要求解。每个f(n-1)，在得到子问题f(n-2)的结果之后需要把结果相加，有n-1次相加操作，所以第二层的操作数是n*(n-1)。
以此类推，到最后一层的子问题是f(1)，会有n*(n-1)(n-2)…2个f(1)。f(1)可以直接返回，操作数是1。所以最后一层的操作数是：$n*(n-1)*(n-2)*...*2*1=n!$n!)。复杂度非常高。

1 找到递归公式画递归树
2 计算每一层在得到子问题的解以后，还要进行哪些操作才能得到本问题的答案，计算这些操作的操作数。
3 考虑树的最长路径和最短路径。
4 分别按照最长路径和最短路径计算所有层的操作数的和。
5 得出时间复杂度范围，推测时间复杂度。