1.2 综合题讲评：从终止不等式反解循环次数

同学，上一课处理了常见选择陷阱。今天的新困难是综合题必须把“循环何时停”翻译成关于执行次数 $k$ 的不等式；若变量不是简单加一，只凭代码层数无法得到可靠结论。

陪做一：

y = 0
while (y+1)*(y+1) <= n:
    y = y+1

执行 $k$ 次后 $y=k$。最后一次能够进入循环意味着 $k^2\le n$，下一次失败意味着 $(k+1{)}^2>n$。因此
$$k=\lfloor \sqrt{n}\rfloor ,$$
时间复杂度为 $\Theta (\sqrt{n})$，额外空间为 $\Theta (1)$。根号来自终止式的平方，不是对数。

陪做二：

i = 1
while i < n:
    j = 0
    while j < i:
        j++
    i = 2*i

外层取值 $1,2,4,\dots ,2^k$，内层总次数是几何和，故为 $\Theta (n)$。如果错误地写成“外层 $\log n$ 乘内层 $n$”，相当于假设每一轮内层都执行 $n$ 次，明显与前几轮状态不符。

陪做三：若循环为 for(i=1;i<n;i++)，循环体只做与输入值无关的常数操作，那么执行 $n-1$ 次，时间为 $\Theta (n)$。某个变量的数值很大，不代表操作次数随它增长；复杂度只追踪问题规模和控制流程。

统一依据是三步：选基本操作；写第 $k$ 次前后的状态；用终止条件反解 $k$ 或对各轮工作量求和。最后再忽略常数和低阶项。

针对性错解：把 $k^2\le n$ 解成 $k\le \log n$ 是代数错误；把嵌套循环的最大单轮工作量直接乘轮数，可能得到过松上界；只报告时间、不说明问题规模或额外空间，综合题过程分不完整。

迁移题：x=1; while x*x*x<=n: x++ 执行多少量级？答案执行 $k$ 次后 $x\approx k+1$，终止边界为 $(k+1{)}^3>n$，所以时间 $\Theta (n^{1/3})$、额外空间 $\Theta (1)$。独立验收是能对三个陌生循环分别写状态表、终止不等式和渐近结论。下一课补齐抽象数据类型的规格表达。