结束了数据结构基本功的学习，接下来在真正开始撸真题之前，大家还需要具备评价算法的能力。

平时我们定义一个人是否“懂行”，一个重要的依据就是看这个人对某一个事物是否具备正确的评价能力。 举个例子，同样是买手机，外行进到手机店，他关注的可能是手机有没有跑马灯、有没有皮套护体、有没有“八心八箭”——这些东西，任何一部手机随便包装一下就都有了，根本没法反映出这台手机的本质问题。但如果是一个相对懂手机的人，他可能就会去关注这台手机的芯片、内存、屏幕材质及分辨率等等，从而对手机的整体性能和质量作出一个合理的判断，这样他买到好手机的概率就更大。

回到做算法题上，也是一样的道理。在面试时，自己给出的算法到底过不过得去，这一点在面试官给出评语之前，自己就应该有所感知。做到这一点，你才会掌握改进算法的主动权。

本节我们要学习的就是评价算法的两个重要依据——时间复杂度和空间复杂度。

很多同学算法入门直接就跪在复杂度理解这一环。时间复杂度、空间复杂度，直接读概念确实太无聊，我们本节从代码入手，大家的理解会更直观一点。

时间复杂度

⚡ 30 秒速记

• 大 O 描述输入规模增大时的渐进上界，不是精确耗时；分析前必须定义 n 代表什么
• 顺序代码复杂度相加取主导项，独立嵌套循环通常相乘，相关循环要按实际总迭代次数求和
• 每轮把问题缩小固定比例通常是 O(log n)，递归还要结合子问题数量和每层工作量
• 哈希 O(1) 常是期望/均摊结论，快排 O(n log n) 常是平均结论，必须带条件
• 数据规模、常数、缓存局部性、I/O 和最坏延迟都会影响工程选型，量级分析后仍需基准测试

时间复杂度描述输入规模增大时，算法执行次数的增长趋势，而不是精确运行时间。 分析前要明确 n 的含义：顺序代码相加后取主导项，独立嵌套循环通常相乘，但相关循环要计算实际总次数。比如内层规模依次减半时，总工作量小于 2n，即使有两层循环仍是 O(n)。递归要同时看分支、规模缩减和每层工作量，工程选型还应结合常数、缓存、I/O 与基准测试。

看到两层循环不能机械报 O(n²)。下面内层总次数是 n + n/2 + n/4 + ... < 2n，因此整体仍为 O(n)：

function halvingWork(items) {
  let operations = 0
  for (let size = items.length; size > 0; size = Math.floor(size / 2)) {
    for (let i = 0; i < size; i += 1) operations += 1
  }
  return operations
}

console.log(halvingWork(Array(8))) // 15

两个前后执行的线性循环是 O(n) + O(n) = O(n)，而不是 O(n²)。矩阵应使用行数 r 与列数 c 表达 O(r × c)，只有二者都等于 n 才写 O(n²)。递归则必须同时分析分支数、规模缩减和每层额外工作。