在前面的学习中，归并排序 与 快速排序 都带有递归的思想，并且时间复杂度都是O(nlogn) ，但并不是有递归的函数就一定是 O(nlogn) 级别的。从以下两种情况进行分析。
① 递归中进行一次递归调用的复杂度分析 二分查找法 1int binarySearch(int arr[], int l, int r, int target){2 if( l > r ) return -1;
3
4 int mid = l + (r-l)/2;
5 if( arr[mid] == target ) return mid;
6 else if( arr[mid] > target )
7 return binarySearch(arr, l, mid-1, target); // 左边
8 else
9 return binarySearch(arr, mid+1, r, target); // 右边
10}
比如在这段二分查找法的代码中，每次在 [ l , r ] 范围中去查找目标的位置，如果中间的元素 arr[mid] 不是 target，那么判断 arr[mid]是比 target 大 还是 小 ，进而再次调用 binarySearch这个函数。
在这个递归函数中，每一次没有找到target时，要么调用 左边 的 binarySearch函数，要么调用 右边 的 binarySearch函数。也就是说在此次递归中，最多调用了一次递归调用而已。根据数学知识，需要log2n次才能递归到底。因此，二分查找法的时间复杂度为 O(logn)。
求和 1int sum (int n) {2 if (n == 0) return 0;
3 return n + sum( n - 1 )
4}
在这段代码中比较容易理解递归深度随输入 n 的增加而线性递增，因此时间复杂度为 O (n)。
求幂 1//递归深度：logn2//时间复杂度：O(logn)
3double pow( double x, int n){
4 if (n == 0) return 1.0;
5
6 double t = pow(x,n/2);
7 if (n %2) return x*t*t;
8 return t * t;
9}
递归深度为 logn，因为是求需要除以 2 多少次才能到底。
② 递归中进行多次递归调用的复杂度分析递归算法中比较难计算的是多次递归调用。
先看下面这段代码，有两次递归调用。
1// O(2^n) 指数级别的数量级，后续动态规划的优化点2int f(int n){
3 if (n == 0) return 1;
4 return f(n-1) + f(n - 1);
5}
递归树中节点数就是代码计算的调用次数。
比如 当 n = 3 时，调用次数计算公式为
1 + 2 + 4 + 8 = 15
一般的，调用次数计算公式为
2^0 + 2^1 + 2^2 + …… + 2^n
= 2^(n+1) - 1
= O(2^n)
与之有所类似的是 归并排序 的递归树，区别点在于
1. 上述例子中树的深度为 n，而 归并排序 的递归树深度为logn。
2. 上述例子中每次处理的数据规模是一样的，而在 归并排序 中每个节点处理的数据规模是逐渐缩小的
因此，在如 归并排序 等排序算法中，每一层处理的数据量为 O(n) 级别，同时有 logn 层，时间复杂度便是 O(nlogn)。
最好、最坏情况时间复杂度