时间复杂度

推导大O阶：

• 顺序执行的代码只会影响常数项，可以忽略
• 对于循环只需挑一个循环中的任意基本操作分析执行次数即可

• 如果有多层嵌套循环，只需关注最深层循环的执行次数

• 很多算法执行时间与输入数据有关，这种需要考虑最好和最坏时间复杂度，以及平均复杂度

• 加法规则 $O(f(n))+O(g(n))=O(\max \{f(n), g(n))\}$

• 乘法规则 $O(f(n)) \times O(g(n))=O(f(n) \times g(n))$

$$O(1)<O\left(\log _{2} n\right)<O(n)<O\left(n \log _{2} n\right)<O\left(n^{2}\right)<O\left(n^{3}\right)<O\left(2^{n}\right)<O(n!)<O\left(n^{n}\right)$$

空间复杂度

程序运行时的内存主要包括程序代码（大小固定）、数据（包括常量、数组）。

• 普通程序：只关注找到所占空间大小与问题规模相关的变量，分析所占空间$x$与问题规模$n$的关系 $x=f(n)$
• 递归程序：找到递归调用的深度$x$与问题规模$n$的关系$x=f(n)$