目标

在浏览器里直接作答 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 节「复杂度入门」再做。题量大，可以分两次完成：先做第 1～10 题，休息后再做第 11～19 题。

作答方法

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

答题进度已答 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 题

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

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 题

递推式 T(n) = 2T(n/2) + n（其中 T(1) = 1）的渐近复杂度是（）

请选择一个答案

AO(n)

BO(n log n)

CO(n²)

DO(log n)

第 11 题

下列递推式中（假设 T(1) = 1），渐近复杂度为 O(n²) 的是（）

请选择一个答案

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 题

若某算法的空间复杂度为 O(1)，则表示该算法（）

请选择一个答案

A不需要任何辅助空间

B所需辅助空间大小与问题规模 n 无关

C不需要任何空间

D所需空间大小与问题规模 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 题是四道对照题）；
• 递归复杂度看「调用次数 × 每次调用代价」：规模减半与规模减 1 天差地别（第 2、14 题）；
• 渐近分析忽略常数与低阶项：20000log₂n 依然比 n 小（第 17 题）。

完成清单

• 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 记法可以忽略对数的底数？（提示：换底公式）

复盘

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