算法时空复杂度分析

Big O 表示法

1、只保留增长速率最快的项，其他的项可以省略。
2、Big O 记号表示复杂度的「上界」。

非递归算法中的时间复杂度分析

这里注意嵌套循环中的时间复杂度。

数据结构 API 的效率衡量方法（摊还分析）

如果想衡量数据结构类中的某个方法的时间复杂度，不能简单地看最坏时间复杂度，而应该看摊还（平均）时间复杂度。

递归算法的时间/空间复杂度的分析方法

递归算法的时间复杂度 = 递归的次数 x 函数本身的时间复杂度

递归算法的空间复杂度 = 递归堆栈的深度 + 算法申请的存储空间

或者再说得直观一点：

递归算法的时间复杂度 = 递归树的节点个数 x 每个节点的时间复杂度

递归算法的空间复杂度 = 递归树的高度 + 算法申请的存储空间