时间复杂度和空间复杂度

通常关注时间复杂度，

对于常数阶和循环次数不变的时空复杂度，就不过多介绍了。

递归的时间复杂度：

对于只调用一次自身且递归次数程常数阶减少的递归，比如：

void fun(int n) {
　　if(n == 0) {
　　    return;
    }
    n--;

    return fun(n);  
}

它的时间复杂度是O(n)，很明显它需要的栈的高度是n，空间复杂度n，因为每个栈都需要存变量。

类推就能得到斐波那契的时间复杂度是O(2^n)，空间复杂度同样O(2^n)。

所以实际项目几乎不允许使用递归，栈的空间本身就不大，递归次数受参数影响呈指数增长，极易栈溢出。

循环复杂度

for(int i = 0; i < n; i ++) {
   i *= 2;  
}

时间复杂度O(lgn)