9.5 程序与代码分析·综合题讲评

回指原理与建模

代码分析先标每个变量语义、循环不变量和边界，再逐语句跟踪。复杂度按基本操作总次数求和，不能只数循环层数。

手工推演与代码证据

嵌套循环外层i倍增、内层执行i次，总量1+2+4+...<2n，因此O(n)，不是O(nlogn)。

代码题必须运行空输入、单元素、一般输入和失败边界；讲评要指出状态为何保持。

错因与迁移

错因是看到两层就相乘最大界。迁移：i*=3且内层i次，几何和仍为O(n)。