目标

在浏览器里直接作答 19 道选择题，练习三步分析法：定义规模 → 数基本操作 → 保留主导项。覆盖 O(1)、O(log n)、O(√n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 等复杂度形态，并包含递推主定理、渐近增长排序与空间复杂度判断，以及「两层循环不一定是 O(n²)」「递归不一定是 2ⁿ」等陷阱题。

建议用时

30～45 分钟，可随 0.2 时间与空间复杂度概论分组完成。每次先写计数依据，再选择答案；不要求在入门阶段提前掌握主定理。

阅读位置	对应题号	重点核验
增长趋势与渐近记号	8、9、17	上界、紧界、常数与低阶项
三角求和与几何步长	15；3、6、13	起止边界、内层上界、实际取值
累计停止与平方边界	4、5、7	第 k 轮状态、最小停止轮数
倍增与折半	1、18、19	整数取整、初值、停止于 1 或 0
峰值辅助空间	12、16	同时存活的数据、统计口径
简单递归	2、14	调用总数与最大活跃深度
第 12 章递推分析	10、11	逐层工作量与主定理条件

代码题默认输入规模非负（题面另有限定时从其限定），整数运算不溢出，基本算术按常数成本计；运行实验时应限制输入范围。若选项使用 O 列出若干量级，选择与实际增长同阶的最紧一项；第 11 题明确用 Θ，避免把有效但较松的上界误当唯一答案。

作答方法

每题先选择一个选项，再点击「提交答案」；提交后立即显示对错，并给出正确答案与详细计算过程。做错的题，先看题解、自己再推一遍，然后点击「重新作答」，直到能独立得出正确答案。

答题进度已答 0/19正确 0

第 1 题

设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（）

c

x = 2;
while (x < n / 2)
    x = 2 * x;

查看提示

写出 x 的前几项：2、4、8、16，再判断达到 n 需要多少次翻倍。

请选择一个答案

AO(log n)

BO(n)

CO(n log n)

DO(n²)

第 2 题

求整数 n（n ≥ 0）阶乘的算法如下，其时间复杂度是（）

c

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

请选择一个答案

AO(log₂n)

BO(n)

CO(n log₂n)

DO(n²)

第 3 题

下列程序段的时间复杂度是（）

c

count = 0;
for (k = 1; k <= n; k *= 2)
    for (j = 1; j <= n; j++)
        count++;

请选择一个答案

AO(log₂n)

BO(n)

CO(n log₂n)

DO(n²)

第 4 题

设 n 为非负整数，下列函数的时间复杂度是（）

c

int func(int n) {
    int i = 0, sum = 0;
    while (sum < n)
        sum += ++i;
    return i;
}

请选择一个答案

AO(log₂n)

BO(√n)

CO(n)

DO(n log₂n)

第 5 题

设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是（）

c

x = 0;
while (n >= (x + 1) * (x + 1))
    x = x + 1;

请选择一个答案

AO(log n)

BO(√n)

CO(n)

DO(n²)

第 6 题

下列程序段的时间复杂度是（）

c

int sum = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

请选择一个答案

AO(log₂n)

BO(n)

CO(n log₂n)

DO(n²)

第 7 题

以下 C 代码的时间复杂度是（）

c

int count = 0;
for (int i = 0; i * i < n; i++)
    for (int j = 0; j < i; j++)
        count++;

请选择一个答案

AO(log₂n)

BO(n)

CO(n log₂n)

DO(n²)

第 8 题

下列关于 T(n) = O(f(n)) 这一记号的说法中，正确的是（）

请选择一个答案

A存在正常数 c 和 n₀，当 n ≥ n₀ 时 T(n) ≤ c·f(n)

B对于所有 n ≥ 1，都有 T(n) ≤ f(n)

CO(2n) 与 O(n) 表示两个不同的复杂度类

DO(n²) ⊆ O(n)，即小复杂度类包含于大复杂度类

第 9 题

设 n 充分大。下列关于复杂度函数渐近增长由慢到快的排序中，错误的是（）

请选择一个答案

AO(1) < O(log n) < O(n) < O(n log n)

BO(n²) < O(n³) < O(2ⁿ) < O(n!)

CO(√n) < O(n) < O(n²)

DO(n log²n) > O(n²)（即 n log²n 渐近大于 n²）

第 10 题

设 n 为 2 的非负整数次幂。递推式 T(n) = 2T(n/2) + n（其中 T(1) = 1）的渐近紧界对应下列哪个量级？

请选择一个答案

AO(n)

BO(n log n)

CO(n²)

DO(log n)

第 11 题

下列递推式中，渐近紧界为 Θ(n²) 的是（）？假设 T(1)=1；含 n/2 的递推在 n 为 2 的幂时讨论。

请选择一个答案

AT(n) = 2T(n/2) + 1

BT(n) = 2T(n/2) + n

CT(n) = 2T(n/2) + n²

DT(n) = T(n-1) + 1

第 12 题

下列关于时间复杂度与空间复杂度的说法中，错误的是（）

请选择一个答案

A算法的空间复杂度通常只考虑辅助空间，不包括输入数据本身所占的存储

B时间复杂度低的算法，其空间复杂度也一定低

C归并排序的时间复杂度为 O(n log n)，但需要 O(n) 的辅助空间

D快速排序平均时间复杂度为 O(n log n)，递归调用栈使其平均空间复杂度为 O(log n)

第 13 题

下列代码段的时间复杂度是（）

c

int count = 0;
for (int i = n; i > 0; i /= 2)
    for (int j = 0; j < i; j++)
        count++;

请选择一个答案

AO(log n)

BO(n)

CO(n log n)

DO(n²)

第 14 题

下列函数 fun 的时间复杂度是（）

c

int fun(int n) {
    if (n <= 1) return 1;
    int a = fun(n / 2);
    int b = fun(n / 2);
    return a + b;
}

请选择一个答案

AO(log n)

BO(n)

CO(n log n)

DO(2ⁿ)

第 15 题

假定 n > 2，执行下面的语句时，语句 S 的执行次数为（）

c

for (i = 1; i < n - 1; i++)
    for (j = n; j >= i; j--)
        S;

请选择一个答案

An(n-1)

B(n+3)(n-2)/2

C(n+2)(n-1)/2

Dn(n-1)/2

第 16 题

设输入为 n 个固定大小的元素，空间复杂度按辅助空间统计。若某算法的空间复杂度为 O(1)，则表示该算法（）

请选择一个答案

A不需要任何辅助空间

B所需辅助空间有一个不随 n 增长的常数上界

C不需要任何空间

D连同 n 个输入元素在内的总空间有一个不随 n 增长的常数上界

第 17 题

下列关于时间复杂度的函数中，时间复杂度最小的是（）

请选择一个答案

AT₁(n) = n log₂n + 5000n

BT₂(n) = n² − 8000n

CT₃(n) = n log₂n − 6000n

DT₄(n) = 20000 log₂n

第 18 题

设 n 是描述问题规模的正整数，则如下程序片段的时间复杂度是（）

c

i = 2;
while (i < n / 3)
    i = i * 3;

请选择一个答案

AO(n³)

BO(n)

CO(∛n)

DO(log₂n)

第 19 题

设 n 是描述问题规模的正整数，则下列程序段的时间复杂度是（）

c

i = n * n;
while (i != 1)
    i = i / 2;

请选择一个答案

AO(log₂n)

BO(√n)

CO(n)

DO(n²)

答案总览（建议完成全部题目后查看）

1. 第 1 题：A
2. 第 2 题：B
3. 第 3 题：C
4. 第 4 题：B
5. 第 5 题：B
6. 第 6 题：B
7. 第 7 题：B
8. 第 8 题：A
9. 第 9 题：D
10. 第 10 题：B
11. 第 11 题：C
12. 第 12 题：B
13. 第 13 题：B
14. 第 14 题：B
15. 第 15 题：B
16. 第 16 题：B
17. 第 17 题：D
18. 第 18 题：D
19. 第 19 题：A

常见陷阱

• 看到两层循环不要直接选 O(n²)——先看内层循环次数是否随外层联动变化（第 3、6、7、13 题是四道对照题）；
• 递归时间累计各调用的非递归工作，不能只看深度；仅当每次调用成本同阶时，才能简化为调用次数乘单次成本（第 2、14 题）；
• 渐近分析忽略常数与低阶项，讨论的是充分大的输入；20000log₂n 并非对每个小 n 都小于 n（第 17 题）；
• 折半的正整数先到 1 再到 0；只改停止值会多一次除法，不会变成平方级（第 19 题）。

完成清单

• 19 道题全部作答，错题的题解都能独立复述
• 能说出「两层循环不一定是 O(n²)」的至少一个反例并解释原因
• 能说出「规模每次减半的递归」与「规模每次减 1 的递归」复杂度上的区别

思考题

1. 第 6 题把内层循环改为 for (int j = 0; j < n; j++)，复杂度变成多少？与第 3 题一致吗？
2. 第 14 题若把 fun(n/2) 的两次调用改成 fun(n-1) 两次，复杂度变成多少？
3. 第 4 题的 while (sum < n) sum += ++i; 改为 while (sum < n) sum += n;，复杂度变成多少？
4. 为什么大 O 记法可以忽略对数的底数？（提示：换底公式）

思考题反馈

1. 数 sum++：第 6 题改后每轮内层 n 次，共 ⌈log₂n⌉ 轮，时间 Θ(n log n)。与第 3 题同阶，但第 3 题的外层是 <=n，在 n 为 2 的幂时多一轮，精确次数不总相同。
2. 对正整数 n，两次 fun(n-1) 的总调用数满足 C(n)=1+2C(n-1)、C(1)=1，解为 2^n-1，时间 Θ(2^n)。兄弟调用依次返回，最大活跃深度为 n，辅助空间 Θ(n)。
3. n>0 时第一次就把 sum 从 0 变成 n，只执行一轮；n=0 时零轮，整体时间 Θ(1)。改变的是每轮增量，不能沿用三角和反推平方根。
4. 对固定常数 a,b>1，log_a n=log_b n/log_b a，分母与 n 无关，故同阶。若底数随 n 改变，这个常数因子论证就不适用。

复盘

• 我常把哪类代码误判成 O(n²)？误判时是漏看了内层循环次数，还是漏看了外层步长？
• 做递推题时，我是否先写出了递推式再套主定理？
• 判断空间复杂度时，我是否先说明了统计口径（是否包含输入本身）？
• 文字描述题和代码题相比，哪个更容易出错？为什么？