算法与复杂度：计算增长次数，而不是押运行秒数

同学，你已经能区分结构和实现。今天的新困难是比较两个算法时，机器、语言和输入都会影响实测时间；我们需要抽掉这些偶然因素，研究基本操作次数如何随问题规模 $n$ 增长。

一个可执行算法至少要有有限性、确定性、可行性，并拥有输入与输出。正确性是底线，随后才比较时间和空间。时间复杂度保留最高阶增长并忽略常数，但必须先说明把哪一步当作基本操作。

陪做：

count = 0
for i = 1 .. n:
    for j = 1 .. i:
        count += 1

第 $i$ 轮内层执行 $i$ 次，总次数
$$T(n)=1+2+\cdots +n=\frac{n(n+1)}{2}.$$
因此 $T(n)=\Theta (n^2)$。依据是上下界都与 $n^2$ 同阶；只写 $O(n^2)$ 虽给了上界，却没有表达这个循环确实达到二次量级。

若改成每轮 $i$ 翻倍：$1,2,4,\dots$，执行轮数满足 $2^k\le n$，所以是 $\Theta (\log n)$。看到循环不应机械数层数，关键是变量怎样逼近边界。

空间复杂度只统计随 $n$ 增长的额外空间。迭代求和使用固定几个变量，额外空间为 $\Theta (1)$；递归求阶乘虽然每层局部变量固定，但调用深度为 $n$，栈空间是 $\Theta (n)$。程序代码本身的固定容量通常不计入增长量。

针对性错解：把两层循环一律判 $n^2$ 会错过内层只运行常数次或指数步进；只算递归函数内一个变量而漏调用栈；比较 $O(n)$ 与 $O(n^2)$ 时忘记小规模常数开销，可能把渐近结论误说成所有 $n$ 下都更快。

迁移题：循环 for(i=1;i<n;i*=2) for(j=0;j<n;j++) op(); 的时间和额外空间是多少？答案外层 $\Theta (\log n)$、内层每次 $\Theta (n)$，总时间 $\Theta (n\log n)$；若只用固定变量，额外空间 $\Theta (1)$。独立验收是能选基本操作、写求和或迭代边界，并分别报告时间和额外空间。下一章将把这些标准用于线性表的不同实现。