众所周知，递归是算法的一个重要表现形式，不仅作用大，而且其复杂度的分析也比其他方式要繁杂。
但是，如果抛开某些很NB，很强大，很邪恶的递归式不谈，如果不能有效的确定普通递归式和一些典型算法递归式的复杂度，那么这个人显然不是合格的Coder。
由于递归式复杂度的难以确定，所以目前常用的方法有这么几种：代换猜测法、递归树法、主定理、直接数学分析法
代换猜测法通常和递归树法合用，利用递归树法得到一个大概正确的结果，然后利用数学归纳法对其验证。
直接的数学分析法相对很直接，很强悍，但是对数学要求很高，尤其是碰到一些BT的表达式
其中，主定理是最常用的方法。
在算法分析中，主定理（master theorem）提供了用渐近符号表示许多由分治法得到的递推关系式的方法。
主定理通常可以解决如下的递归表达式：
T(n)=a*T（n/b）+f（n）
上面的递归式描述的是将规模为n的问题划分为a个子问题，并且每个子问题的规模是n/b，这里a和b是正常数。划分原问题和合并结果的代价有函数f(n)描述。
主定理有三种情况，不同的情况有不同的用法。
一些非正常情况
在某些情况下，存在一些特殊情况，比如明显不满足主定理形式，或经过乍看之下不满足，但是经过变形之后可以应用主定理。
甚至在某些情况下，看上去符合主定理的递归式是无法应用主定理求解的，因为主定理不覆盖所有情况，即递归式不满足上面三条中的任意一条
我们逐一来看看这些特殊情况
这种形式的条件显然不符合主定理的口味，但是我们可以简单的通过递归树加上一点点的数学分析可知，总共有n层，每层都是n的代价，所以总代价应该是O(n2)
n带了根号，乍看之下是无法应用主定理的，但是我们可以通过换元等trick将递归式转化成可以用主定理求解的式子
而对于某些式子，如上面所说，看着似乎可以用MM求解，但是实际上不满足3条中的任何一条，比如下面的：
常见递归算法的复杂度
我们经常碰到的算法中，很多都是基于递归的，比如快速排序、归并排序、二分查找等等，甚至你也可以把求Fibonaci数列的递归算法也算入
而这些递归式都是很容易分析的，分析的过程就留给大家了～