02　计算量与时间复杂度

基本操作、增长阶、最好最坏与摊销

对应本节 12 道题。点击题目展开答案和理由，保留此前生成的详细解析。

第 01 题　保留最高阶项

某算法的基本操作次数为 3n² + 7n + 20。请写出它的时间复杂度，并说明判断时为什么可以忽略另外两项。

答案：O(n²)

操作次数为 3n² + 7n + 20。
当 n 增大时，n² 项比 n 项和常数项增长得快得多。
渐进分析忽略常数倍和低阶项，因此保留最高阶项，得到 O(n²)。

系数 3 不改变增长阶；当输入规模很大时，7n 和 20 相对于 n² 的影响逐渐变小。

第 02 题　比较增长速度

把下列时间复杂度按“增长由慢到快”排列，选择正确的一项。

A. O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) B. O(1)、O(n)、O(log n)、O(n²)、O(n log n)、O(2ⁿ) C. O(log n)、O(1)、O(n)、O(n log n)、O(2ⁿ)、O(n²) D. O(1)、O(log n)、O(n log n)、O(n)、O(n²)、O(2ⁿ)

答案：A

从慢到快为：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。

直觉上，常数时间不随 n 增长；对数时间每轮大幅缩小待处理规模；线性时间随数据量成比例增长；平方时间来自常见的双重全量循环；指数时间的增长很快，n 稍大就会变得昂贵。

第 03 题　单层循环

分析下面代码的时间复杂度，并说明循环体执行了多少次。

for i in range(n):
    total += i

答案：循环体执行 n 次；时间复杂度 O(n)

range(n) 依次产生 n 个值，循环体每轮只做常数时间的加法。总操作数与 n 成正比，所以是 O(n)。

第 04 题　两层循环

分析下面代码的时间复杂度。假设每次执行 count += 1 都是一次基本操作，请先写出操作总次数。

for i in range(n):
    for j in range(n):
        count += 1

答案：基本操作共 n² 次；时间复杂度 O(n²)

外层循环执行 n 次。
外层每执行一轮，内层也执行 n 次。
总次数为 n × n = n²，因此复杂度是 O(n²)。

两个循环嵌套时，内层工作会对外层的每一轮重复执行。

第 05 题　循环次数随外层变化

分析下面代码。内层循环执行总次数是多少？时间复杂度是什么？

for i in range(n):
    for j in range(i + 1):
        count += 1

答案：总次数为 n(n + 1) / 2；时间复杂度 O(n²)

当 i = 0 时，内层执行 1 次；i = 1 时执行 2 次；依此类推；i = n − 1 时执行 n 次。
总次数为 1 + 2 + … + n = n(n + 1) / 2。
展开得到 (n² + n) / 2。忽略常数和低阶项后是 O(n²)。

第 06 题　每轮缩小一半

当 n 大于 1 时，下面的循环每次把 n 除以 2（整数除法）。循环大约执行多少轮？时间复杂度是什么？

while n > 1:
    n = n // 2

答案：大约执行 log₂ n 轮；时间复杂度 O(log n)

执行 k 轮后，数值大约变成 n / 2ᵏ。当它缩小到 1 左右时循环停止，所以 n / 2ᵏ ≈ 1，即 2ᵏ ≈ n，因此 k ≈ log₂ n。

对数的底数在渐进复杂度中只相差常数倍，所以通常写作 O(log n)。

第 07 题　不同规模的两段工作

第一个循环执行 n 次，第二个循环执行 m 次；两个循环前后顺序执行，循环体都是常数时间。请写出总时间复杂度。如果 n 与 m 相等，结果可进一步简化为什么？

答案：一般情况 O(n + m)；若 n = m，则为 O(n)

两段工作前后执行，操作总数是 n + m，所以一般写作 O(n + m)。如果 n 和 m 相等，总数变成 2n；忽略常数因子后是 O(n)。

顺序执行的两段工作相加；嵌套循环则要把内外层的迭代次数相乘。

第 08 题　二分查找

对一个有序数组执行二分查找。分别写出：①最好情况下的时间复杂度；②最坏情况下的时间复杂度；③最坏情况下每一步为什么只需继续检查约一半元素？

答案：最好 O(1)；最坏 O(log n)

最好情况下，目标正好是第一次检查的中间元素，只需常数次操作，故为 O(1)。
最坏情况下，每次比较后都继续搜索剩下的一半。经过 k 步，候选范围约为 n / 2ᵏ。
范围缩小到 1 个元素时，2ᵏ ≈ n，所以最多需要约 log₂ n 步，即 O(log n)。

二分查找要求数据已经按查找所需的顺序排列。

第 09 题　递归调用

函数每次把 n 减 1，再递归调用自己，直到 n ≤ 1 才结束。假设每次调用除递归调用外只做常数时间的工作。请分别写出时间复杂度和递归调用栈占用的额外空间复杂度。

答案：时间 O(n)；递归栈额外空间 O(n)

每次调用把 n 减少 1，直到 n ≤ 1，因此递归深度与 n 成正比。
每层只做常数时间的工作，总工作量约为 n 层，时间复杂度是 O(n)。
在递归返回前，这些调用需要保存在调用栈中；最多同时存在约 n 层，因此额外空间是 O(n)。

递归算法的时间复杂度和空间复杂度要分别分析：调用次数看时间，最大同时保留的调用层数看栈空间。

第 10 题　线性循环套对数循环

分析下面代码的时间复杂度和额外空间复杂度。内层变量每次乘以 2。

for i in range(n):
    j = 1
    while j < n:
        j *= 2

答案：时间 O(n log n)；额外空间 O(1)

外层循环执行 n 次。
每次外层循环开始时，j 从 1 出发并不断乘以 2。j 的值依次为 1、2、4、8……，达到 n 需要约 log₂ n 次，所以内层是 O(log n)。
内层工作对外层的每一轮重复，时间复杂度为 O(n × log n) = O(n log n)。
只使用 i 和 j 等少量变量，没有随 n 增长的额外容器，因此额外空间为 O(1)。

第 11 题　补充练习

一次动态数组扩容会复制 O(n) 项，为什么连续末尾追加仍可摊销 O(1)？

参考答案

容量按固定倍数增长时，连续 n 次追加总工作 O(n)。

解析

把多次扩容的几何级数复制成本分摊到全部追加，而不是把单次最坏和序列摊销混为一谈。

第 12 题　补充练习

为了 q 次按键查询先建索引，为什么分析时还要计算建索引与存储？

参考答案

完整任务包含准备 O(n) 时间和通常 O(n) 额外空间。