非递归算法分析
例1：如果算法的执行时间不随着问题规模n的增加而增长，它的基本语句执行的次数是固定的，总的时间由一个常数来限界。此类算法的时间复杂度是O(1)。
例2：当有若干个循环语句时，时间复杂度是由嵌套层数最多的循环语句中的基本语句的执行次数决定。
void fun(int n){
int x=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
for(int k=1;k<=j;k++){
x++; //基本语句
}
}
}
}
fun函数的时间复杂度为O(n ^ 3)。
虽然非递归算法的时间复杂度比较好分析，但往往需要用到多项式的求和技巧和放缩技巧，如：
image.png
递归时间复杂度分析
代入法
代入法首先要对这个问题的时间复杂度做出预测，然后将预测带入原来的递归方程，如果没有出现矛盾，则是可能的解，最后用数学归纳法证明。
【举 例】我们有如下的递归问题：T(n)=4T(n/2)+O(n)，我们首先预测时间复杂度为O(n2),不妨设T(n)=kn2（其中k为常数），将该结果带入方程中可得：左=kn2，右=4k(n/2)2+O(n)=kn2+O(n),由于n2的阶高于n的阶，因而左右两边是相等的，接下来用数学归纳法进行验证即可。
迭代法
迭代法就是迭代的展开方程的右边，直到没有可以迭代的项为止，这时通过对右边的和进行估算来估计方程的解。比较适用于分治问题的求解，为方便讨论起见，给出其递归方程的一般形式：
image
【举 例】下面我们以一个简单的例子来说明：T(n)=2T(n/2)+n2,迭代过程如下：
image
容易知道，直到n/2^(i+1)=1时，递归过程结束，这时我们计算如下：
image
到这里我们知道该算法的时间复杂度为O(n2)，上面的计算中，我们可以直接使用无穷等比数列的公式，不用考虑项数i的约束，实际上这两种方法计算的结果是完全等价的，有兴趣的同学可以自行验证。
公式法（主方法）
这个方法针对形如：T(n) = aT(n/b) + f(n)的递归方程。这种递归方程是分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子问题，递归地求解这a个子问题，然后通过对这a个子问题的解的综合，得到原问题的解。这种方法是对于分治问题最好的解法，我们先给出如下的公式：
image
公式记忆：我们实际上是比较n^logba和f(n)的阶，如果他们不等，那么T(n)取他们中的较大者，如果他们的阶相等，那么我们就将他们的任意一个乘以logn就可以了。按照这个公式，我们可以计算【迭代法】中提到的例子：O(f(n))=O(n2),容易计算另外一个的阶是O(n),他们不等，所以取较大的阶O(n2)。太简单了，不是吗？
需要注意：上面的公式并不包含所有的情况，比如第一种和第二种情况之间并不包含下面这种情况：f(n)是小于前者，但是并不是多项式的小于前者。同样后两种的情况也并不包含所有的情况。为了好理解与运用的情况下，笔者将公式表述成如上的情况，但是并不是很严谨，关于该公式的严密讨论，请看这里。但是公式的不包含的情况，我们很少很少碰到，上面的公式适用范围很广泛的。
特别地，对于我们经常碰到的，当f(n)=0时，我们有：
image
递归树
递归树是一棵结点带权值的树。初始的递归树只有一个结点，它的权标记为T(n)；然后按照递归树的迭代规则不断进行迭代，每迭代一次递归树就增加一层，直到树中不再含有权值为函数的结点（即叶结点都为T(1)）。下面以递归方程
image.png
来讲述递归树的迭代规则。
image.png
image.png
递归树的高度为lg n，每层时间复杂度相加得到总的时间复杂度为O(lgn * cn)，即O(n * lg n)
总结：递归树模型求解递归方程，本质上就是迭代思想的应用，利用递归方程迭代展开过程构造对应的递归树，然后把每层的时间代价进行求和。不过递归树模型更直观，同时递归树也克服了二阶及更高阶递推方程不方便迭代展开的痛点。
zz: http://www.cnblogs.com/python27/archive/2011/12/09/2282486.html
空间复杂度分析
空间复杂度(Space Complexity)是在程序中除了输入输出以外所需要用的内存空间大小，无论这个内存如何分配，分配到哪里，不应该影响空间复杂度的取值。空间复杂度记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。
对于递归方法来说，递归的空间复杂度至少是O(h)，h为递归深度。当然，或许你的面试官会有不同意见，所以你可以说：“The program takes O(N) space on the call stack. So if that counts, the space complexity should be ... ”。这样既不会给出错误答案，又表示你确实知道这个内存分配发生在什么地方。
网友评论