2-5 递归算法的复杂度分析
递归算法的复杂度分析
不是有递归的算法的时间复杂度都为O(nlogn)！
递归中进行一次递归调用的复杂度分析
如果递归函数中，只进行一次递归调用，递归深度为depth；
在每个递归函数中，时间复杂度为T；
则总体的时间复杂度为O(T * depth)
递归中进行多次递归调用的复杂度分析
归并排序用的就是分治法的思想，数组长度为n，每层计算的事件复杂度为O(n)，树的深度为O(logn)，因此总的时间复杂度为O(nlogn)。
主定理
主定理，归纳了递归函数的时间复杂度的所有情况，一个递归函数把数据分成几份进行递归， 每一份里面的时间复杂度是多少，对于不同的情况，主定理都给出了答案。
面试中不会涉及到主定理的考察，感兴趣的同学可以研究一下。