时间复杂度和空间复杂度

时间复杂度和空间复杂度常被用来衡量算法消耗的资源和时间，从而判断算法的优劣。

时间复杂度

时间复杂度用来衡量算法的计算时间，用渐近符号（大O符号）进行表示。常见的时间复杂度如下：

O(1) constant complexity
O(logn) logarithmic complexity
O(n) linear complexity
O(nlogN) 线性对数阶
O(n^2) N square complexity
O(n^3) N cubic complexity
O(2^n) exponential growth
O(n!) factorial 阶乘

对于简单的情况，可利用算法中的循环次数判断其时间复杂度。在计算时间复杂度时，运算次数为
$2n^2, 4n^2$

等的算法的时间复杂度均为
$O(n^2)$

，其前的常数在判断时可忽略。
对于递归情况，可画出递归状态的递归树辅助判断。也可利用主定理 (master theorem)直接进行计算。

斐波那契数列递归

主定理

推导参考主定理 Master Theorem。

常用算法的主定理应用

空间复杂度

空间复杂度用来衡量算法需要的资源如存储容量。
一般来说，算法的空间复杂度为代码中建立的数组的长度，
对于递归的情况，其空间复杂度为递归的深度。