02　计算量与时间复杂度

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

本节 12 题。先独立给出结论和理由，再对照解析；新增题与此前题目统一编号。涉及标签时，标签只表示记录身份。

第 01 题

保留最高阶项

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

第 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ⁿ)

第 03 题

单层循环

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

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

第 04 题

两层循环

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

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

第 05 题

循环次数随外层变化

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

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

第 06 题

每轮缩小一半

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

while n > 1:
    n = n // 2

第 07 题

不同规模的两段工作

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

第 08 题

二分查找

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

第 09 题

递归调用

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

第 10 题

线性循环套对数循环

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

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

第 11 题

补充练习

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

第 12 题

补充练习

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