算法复杂度分析

数据结构和算法解决的是快和省的问题，即如何让代码运行得更快，更省存储空间。 可以用时间、空间复仇度分析来衡量算法好坏。

大 O 复杂度表示法

所有代码的执行时间T(n)与每行代码的执行次数f(n)成正比

$T(n) = O(f(n))$

大O时间复杂度表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度。

时间复杂度分析

1. 只关注循环执行次数最多的一段代码

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见复杂度案例

1. 多项式量级

   • 常量阶$O(1)$
   • 对数阶$O(log_n)$
   • 线性阶$O(n)$
   • 线性对数阶$O(nlog_n)$
   • 平方阶$O(n^2)$、立方阶$O(n^3)$…k 次方阶$O(n^k)$

2. 非多项式量级

   • 指数阶$O(2^n)$
   • 阶乘阶$O(n!)$

(最好/最坏)情况时间复杂度

在(最理想/最糟糕)的情况下，执行这段代码的时间复杂度。

平均情况时间复杂度

将各种情况发生的概率考虑进去，做加权平均。

均摊时间复杂度

特殊的平均时间复杂度

每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。

空间复杂度分析

空间复杂度全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。