程序员数学 03：计数、增长与复杂度

“有两层循环，所以是平方复杂度”有时正确，有时不正确。更可靠的方法是明确输入规模 $n$，数清关键操作执行多少次，再分析它随 $n$ 的增长。

从两两比较数起

给 $n$ 条记录做不重复的两两比较，第 1 条需要比较 $n-1$ 次，第 2 条需要 $n-2$ 次，最后一条为 0 次。

$$T(n)=(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}.$$

这是组合数 $(\genfrac{}{}{0ex}{}{n}{2})$。当 $n=1000$ 时为 499,500 次；当 $n=10,000$ 时为 49,995,000 次，输入扩大 10 倍，比较次数接近扩大 100 倍。

let comparisons = 0;
const n = 5;
for (let i = 0; i < n; i++) {
  for (let j = i + 1; j < n; j++) comparisons++;
}
console.log(comparisons); // 10

如果对象排列顺序重要且不允许重复选择，数量是 $n(n-1)$；如果允许自己与自己配对且顺序重要，数量是 $n^2$。做计数前先确认“顺序”和“重复”是否有意义。

对数来自重复缩小

把候选范围每次减半，经过 $k$ 次后规模约为 $n/2^k$。要缩小到常数量级，需要 $k$ 约为 ${\log }_{2}n$。因此在已排序、可常数时间随机访问的数组上，二分查找的比较次数为 $\mathrm{\Theta }(\log n)$。

但如果为了只查一次就先排序，排序成本也要算进去；如果容器不能高效定位中点，只数比较次数又不足以解释总成本。复杂度是基于操作成本假设的模型。

两层循环也可能是 n log n

let steps = 0;
const size = 8;
for (let i = 0; i < size; i++) {
  for (let j = 1; j < size; j *= 2) steps++;
}
console.log(steps); // 24

内层取 $1,2,4$，执行 3 次；一般执行 $\lceil {\log }_{2}n\rceil$ 次（$n\ge 1$）。乘上外层 $n$，得到 $\mathrm{\Theta }(n\log n)$。若内层改成 j++，才变成 $\mathrm{\Theta }(n^2)$。

O、Θ 与实测分别回答什么

$O(f(n))$ 给渐近上界，$\mathrm{\Theta }(f(n))$ 给同阶上下界。$3n+10$ 属于 $O(n)$，也属于较松的 $O(n^2)$，通常用 $\mathrm{\Theta }(n)$ 表达其紧确增长阶。

这些符号不会告诉你具体运行几毫秒。常数、缓存、I/O、并行、运行时和数据分布都影响实际耗时。应同时写清最坏、平均还是摊还情况。例如哈希查找常用预期常数时间模型，但这不代表任意哈希实现、任意碰撞输入都保证最坏常数时间。

练习

1. 20 个不同对象，不计顺序、不重复选取，选两个有几种方式？
2. 先遍历 $n$ 个元素，再遍历 $n$ 个元素，是平方增长吗？
3. 一次准备成本为 1000 单位，每次查询从 10 降至 2 单位，至少查询多少次才比原方案严格便宜？

查看答案与讲解

1. $20\times 19/2=190$。
2. 不是，总次数 $2n$，是线性增长；“先后相加”不同于“每个外层都执行全部内层”。
3. 要求 $1000+2q<10q$，所以 $q>125$，整数查询次数至少 126。这里假设每次查询成本固定，实际使用应测量。

资料与延伸

MIT 6.006 算法讲义 提供算法分析与数据结构材料。进一步学习时，把时间、额外空间和预处理成本分别列出来。