算法分析之复杂度

算法复杂度分析，是从理论角度衡量一个算法的性能指标，包括时间复杂度和空间复杂度

大 O 表示法：渐进时间（空间）复杂度，表示代码运行时间（占用空间）随问题规模增长的变化趋势

时间复杂度

$O(\log n)$代码示例：

let i=1;
while (i <= n)  {
   i = i * 2;
}

常见时间复杂度大小关系：

$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

时间复杂度分类：

1. 最好情况时间复杂度
2. 最坏情况时间复杂度
3. 平均情况时间复杂度
4. 均摊时间复杂度：基本不用，略过

一般说时间复杂度，都指最坏情况时间复杂度

空间复杂度

我们常见的空间复杂度就是 $O(1)、O(n) 、O(n^2)$