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

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

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

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

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

时间复杂度

⚡ 30 秒速记

• 大 O 描述「数据量变大时执行次数怎么涨」，不是具体多少毫秒；先说清 n 是什么
• 前后两段相加取大头，嵌套循环通常相乘，但内层跟外层相关时要算实际总次数
• 每轮把问题砍掉一半或乘 2 推进 → O(log n)
• 内层规模逐轮减半：n + n/2 + n/4 + ... < 2n，两层循环也是 O(n)
• 哈希 O(1) 是平均，快排 O(n log n) 也是平均，最坏 O(n²)，报复杂度要带条件

时间复杂度说的是数据量变大的时候，代码执行次数按什么趋势涨，而不是跑了多少毫秒。 比如遍历一个数组，执行次数大约是 3n + 3，常数和低次项都扔掉，就是 O(n)。最常见的误区是数循环层数：两层循环不一定是 O(n²)，要看内层实际跑了多少次，内层规模每轮减半的话总共不到 2n 次，还是 O(n)。另外 O(1) 的哈希查找、O(n log n) 的快排都是平均情况，面试时报复杂度我会顺带说一下是最坏还是平均。

看到两层循环不能机械报 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²)。递归则必须同时分析分支数、规模缩减和每层额外工作。