1.2 选择题讲评：复杂度先写次数关系再看选项

同学，你已经会用求和分析复杂度。今天的新困难是选择题常把算法基本特性、好算法的评价标准和复杂度计算混在一起，还会用特殊循环让“两层就是平方”的直觉失效。稳定做法是先独立算，再看选项。

第一类概念题：有限性、确定性、可行性、输入和输出是算法成立的基本特性；正确性、可读性、健壮性、效率与低存储需求是评价算法好坏的常见标准。若题问“算法必须具备”，不能把“效率高”选进去，因为低效但有限且明确的步骤仍可能是算法。

陪做倍增循环：

i = 1
while i <= n:
    i = 2*i

第 $k$ 次循环前 $i=2^{k-1}$，终止条件给 $2^k>n$，所以执行次数为 $\lfloor {\log }_{2}n\rfloor +1=\Theta (\log n)$。依据是循环变量按乘法增长，不能按 $1,2,3,\dots ,n$ 去数。

再看两层循环：外层 $i=1,2,4,\dots ,2^k<n$，内层执行 $i$ 次。总次数
$$1+2+4+\cdots +2^k=2^{k+1}-1.$$
由于 $2^k<n\le 2^{k+1}$，总量是 $\Theta (n)$，不是看到两层就选 $\Theta (n\log n)$。

递归题则写调用次数或递推式。若 $f(n)$ 每次只调用 $f(n-1)$ 并做常数工作，$T(n)=T(n-1)+O(1)=O(n)$；若出现两个规模近半的调用，结构会完全不同。

针对性错解：把“至少一个输入”当算法必需条件会忽略零输入算法；循环条件只看变量名不列取值表，容易把对数、根号和线性混淆；复杂度保留低阶项或常数系数，则没有抓住渐近增长。

迁移题：for(i=1;i<=n;i*=3) for(j=0;j<i;j++) op(); 的时间复杂度是什么？答案总次数为 $1+3+\cdots +3^k=(3^{k+1}-1)/2=\Theta (n)$。独立验收是能对一组概念选项先归类，对每段循环列前三个取值并写出等式或求和，再选择答案。下一课集中处理需要完整书写过程的复杂度综合题。