算法复杂度分析
递推算法
对于递推类和循环类算法，我们一般统计其主要的基本操作个数与问题的规模大小。从而就可以推出算法复杂度。
递归算法
- 对于任意
α!=1 的通式T(n)=T(αn)+T((1−α)n)+cn ，其时间复杂度都是O(nlogn) - 对于范式
T(n)=aT(n/b)+nd ,对于a>1,b>1,d>0 ,所以可以得出最后的复杂度为：
对上面分析，当d>logba 时，那么abd 就小于1，所以1+abd+(abd)2+.......+(abd)logbn 的和极限一定小于某个常数，即T(n)<C∗nd ，所以T(n)=nd .
当d=logba 时，那么1+abd+(abd)2+.......+(abd)logbn 等于logbn ,所以这个时候T(n)=nlogbalogn .
当d<logba 时，那么abd 就大于1，所以1+abd+(abd)2+.......+(abd)logbn 的和是一个随n的线性增长，即T(n)<nlogba ，所以T(n)=nlogba .
双层递推
如：
对于此类问题的分解：
采用求取特征值的求法:
这样转换的原因在于，呈现上述公式的解一般是指数型解可以化简，这样x就相当于指数基数了。这样就可以最终求出
特殊形式
当