能做对这二十道时间复杂度分析吗

在算法的世界里，时间复杂度分析是评估算法效率的核心标尺。它描述了算法的执行时间随输入数据规模增长而变化的趋势，是我们在有限的时间和内存资源下，设计出高效解决方案的关键。

本文将通过20个精心挑选的题目，涵盖从基础到进阶的各种情况，包括选择、判断、代码阅读和填空。无论你是初学者还是有一定经验的选手，都可以通过这些题目来检验和巩固自己对时间复杂度分析的理解。

一、基本概念与大O表示法

在深入题目之前，我们首先需要明确什么是时间复杂度。简单来说，时间复杂度是算法运行所需要的基本操作次数的函数。我们通常使用大O表示法（Big O notation）来描述这个函数。

大O表示法关注的是当输入规模 $n$ 趋向于无穷大时，算法执行时间的增长率。它忽略了常数项、低阶项和系数，只保留对增长趋势影响最大的那一项。例如，一个算法的精确执行步数是 $T(n) = 3n^2 + 5n + 100$，我们称其时间复杂度为 $O(n^2)$。

常见的时间复杂度量级（从低到高）包括：

• 常数阶 $O(1)$：执行时间不随输入规模 $n$ 的变化而变化。
• 对数阶 $O(\log n)$：执行时间随 $n$ 的对数增长。
• 线性阶 $O(n)$：执行时间与 $n$ 成正比。
• 线性对数阶 $O(n \log n)$：通常与排序算法相关。
• 平方阶 $O(n^2)$：常见于嵌套循环。
• 立方阶 $O(n^3)$：常见于更深层次的嵌套循环。
• 指数阶 $O(2^n)$：通常与递归的暴力搜索相关。
• 阶乘阶 $O(n!)$：与全排列等问题相关。

现在，让我们用具体的题目来实践这些概念。

二、练习题

题目 1

下列哪个函数在 $n$ 趋于无穷大时增长最快？

A. $f(n) = n \log_2 n$ B. $g(n) = n^2$ C. $h(n) = 2^n$ D. $k(n) = n!$

分析： 这是一个基础的增长率比较问题。我们需要知道不同函数量级之间的关系。阶乘函数 $n!$ 的增长速度远快于指数函数 $2^n$。指数函数 $2^n$ 的增长速度快于多项式函数 $n^2$。而多项式函数 $n^2$ 的增长速度快于线性对数函数 $n \log_2 n$。因此，增长最快的函数是 $k(n) = n!$。

$$O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < \dots < O(2^n) < O(n!) $$

答案：D

题目 2

算法的时间复杂度为 $O(n^2)$，表明该算法的？

A. 执行时间等于 $n^2$ B. 执行时间和 $n^2$ 成正比 C. 执行时间在 $n^2$ 的常数倍以内 D. 问题规模是 $n^2$

分析： 大O表示法提供的是一个渐进上界。$T(n) = O(n^2)$ 意味着存在正常数 $c$ 和 $n_0$，使得对于所有 $n \ge n_0$，都有 $T(n) \le c \cdot n^2$。这表明算法的执行时间不会超过 $n^2$ 的某个常数倍。它不意味着严格成正比，更不意味着相等。

答案：C

题目 3

一个算法的时间复杂度为 $O(1)$，这意味着什么？

A. 无论问题规模多大，始终在一秒内执行完。 B. 算法只需要1秒就能执行完毕。 C. 算法中没有循环和递归。 D. 算法的执行时间与问题规模无关。

分析： $O(1)$ 表示常数时间复杂度。这意味着算法的执行时间不随输入规模 $n$ 的变化而变化。即使输入是1百万或1亿，执行时间也保持不变。注意，这并不意味着执行时间很短，只是说它是一个不依赖于 $n$ 的常数。一个算法即使有循环，只要循环次数是常数（如 for (int i = 0; i < 100; ++i))，其复杂度依然是 $O(1)$。

答案：D

题目 4

分析以下代码片段的时间复杂度：

void f(int n) {
    int c = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            c += 1;
        }
    }
}

A. $O(n)$ B. $O(n \log n)$ C. $O(n^2)$ D. $O(1)$

分析： 该代码包含一个嵌套循环。外层循环执行 $n$ 次。对于外层循环的每一次迭代，内层循环也执行 $n$ 次。因此，总的执行次数是 $n \times n = n^2$ 次。所以时间复杂度为 $O(n^2)$。

答案：C

题目 5

分析以下递归函数的时间复杂度：

int f(int n) {
    if (n <= 1) {
        return 1;
    }
    return f(n - 1) + f(n - 1);
}

A. $O(n)$ B. $O(n^2)$ C. $O(2^n)$ D. $O(\log n)$

分析： 这是一个经典的递归复杂度分析。我们可以写出其递归关系式：$T(n) = 2T(n-1) + O(1)$。 我们将这个递推式展开： $T(n) = 2T(n-1) + 1$ $= 2(2T(n-2) + 1) + 1 = 4T(n-2) + 2 + 1$ $= 4(2T(n-3) + 1) + 3 = 8T(n-3) + 4 + 2 + 1$ ... $= 2^k T(n-k) + (2^{k-1} + \dots + 2^1 + 2^0)$ 当 $n-k=1$ 时，即 $k=n-1$ 时， $T(n) = 2^{n-1} T(1) + (2^{n-1} - 1)$ $T(n) = O(2^n)$。

这形成了一个高度为 $n$ 的满二叉树调用结构，总的调用次数是 $1+2+4+\dots+2^{n-1} = 2^n - 1$。因此，时间复杂度为 $O(2^n)$。

答案：C

题目 6

判断：一个算法的时间复杂度是 $O(n)$，另一个是 $O(n^2)$，则在任何情况下，前者的执行速度都比后者快。

分析： 这个说法是错误的。大O表示法描述的是渐进趋势。对于较小的输入规模 $n$，$O(n^2)$ 的算法可能由于其常数因子更小而运行得更快。例如，一个算法执行 $100n$ 次操作，另一个执行 $n^2$ 次操作。当 $n < 100$ 时，$n^2 < 100n$，后者更快。只有当 $n$ 足够大时，$O(n)$ 的算法才会展现出其优势。

答案：错误

题目 7

判断：二分查找算法的时间复杂度是 $O(\log n)$。

分析： 正确。二分查找（Binary Search）在每一步都将搜索空间减半。对于一个大小为 $n$ 的有序数组，查找过程最多需要进行 $\log_2 n$ 次比较。具体来说，假设经过 $k$ 次操作后，剩余元素数量为1，则有 $n/2^k = 1$，解得 $k = \log_2 n$。因此，时间复杂度为 $O(\log n)$。

答案：正确

题目 8

判断：对一个包含 $n$ 个元素的无序数组，找到其中最大值的时间复杂度是 $O(1)$。

分析： 错误。为了在无序数组中找到最大值，你必须遍历每一个元素至少一次，以确保没有遗漏任何一个可能的最大值。这个过程需要 $n-1$ 次比较。因此，操作次数与数组大小 $n$ 呈线性关系，时间复杂度为 $O(n)$。

答案：错误

题目 9

判断：如果一个算法由两个独立的步骤组成，第一步的时间复杂度为 $O(n^2)$，第二步的时间复杂度为 $O(n \log n)$，那么该算法的总时间复杂度为 $O(n^2)$。

分析： 正确。对于顺序执行的几个部分，总的时间复杂度由其中复杂度最高的那个部分决定。这被称为“加法原则”。总时间 $T(n) = T_1(n) + T_2(n) = O(n^2) + O(n \log n)$。由于 $n^2$ 的增长率高于 $n \log n$，我们取最高阶项，所以总复杂度为 $O(n^2)$。

答案：正确

题目 10

判断：map (或 std::map in C++) 这种基于平衡二叉搜索树的数据结构，其插入、删除、查找操作的平均和最坏时间复杂度都是 $O(\log n)$。

分析： 正确。std::map 在C++中通常由红黑树（一种自平衡二叉搜索树）实现。这种数据结构通过旋转等操作来维持树的平衡，确保树的高度大致保持在 $\log n$ 的量级。因此，无论是插入、删除还是查找操作，其路径长度都与树的高度成正比，时间复杂度为 $O(\log n)$。

答案：正确

题目 11

题意概括：分析一个循环，其循环变量以乘法方式增长。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void f(int n) {
    int i = 1;
    while (i < n) {
        i = i * 2;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // ...
    return 0;
}

分析： 观察循环变量 i 的变化：1, 2, 4, 8, 16, ... 这是一个以2为底的指数序列。假设循环执行了 $k$ 次，那么第 $k$ 次循环后 i 的值是 $2^k$。循环的终止条件是 $i \ge n$。所以我们需要找到最小的 $k$ 使得 $2^k \ge n$。两边取对数，得到 $k \ge \log_2 n$。因此，循环的执行次数与 $\log_2 n$ 成正比。时间复杂度为 $O(\log n)$。

答案：$O(\log n)$

题目 12

题意概括：分析一个嵌套循环，内层循环的次数依赖于外层循环的变量。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void f(int n) {
    int c = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            c += 1;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // ...
    return 0;
}

分析： 外层循环变量 i 从 $0$ 到 $n-1$。 当 i = 0 时，内层循环执行 $n$ 次（j 从 0 到 n-1）。 当 i = 1 时，内层循环执行 $n-1$ 次（j 从 1 到 n-1）。 ... 当 i = n-1 时，内层循环执行 $1$ 次（j 从 n-1 到 n-1）。

总的执行次数为 $n + (n-1) + (n-2) + \dots + 1$，这是一个等差数列求和。

$$\text{Total} = \frac{(n+1)n}{2} = \frac{1}{2}n^2 + \frac{1}{2}n $$

根据大O表示法，我们忽略常数系数和低阶项，得到时间复杂度为 $O(n^2)$。

答案：$O(n^2)$

题目 13

题意概括：分析一个带有开方运算的循环条件。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void f(int n) {
    int i = 0;
    while (i * i < n) {
        i++;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // ...
    return 0;
}

分析： 循环的终止条件是 i * i >= n，等价于 $i \ge \sqrt{n}$。循环体内的操作 i++ 是 $O(1)$ 的。循环从 $i=0$ 开始，每次加1，直到 $i$ 大约等于 $\sqrt{n}$ 时停止。因此，循环的执行次数约为 $\sqrt{n}$ 次。时间复杂度为 $O(\sqrt{n})$。

答案：$O(\sqrt{n})$

题目 14

题意概括：分析一个双指针相关的代码片段。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int f(int n, int arr[]) {
    int l = 0, r = n - 1, ans = 0;
    while (l < r) {
        if (arr[l] + arr[r] < 100) {
            l++;
        } else if (arr[l] + arr[r] > 100) {
            r--;
        } else {
            ans++;
            l++;
            r--;
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // ...
    return 0;
}

分析： 这段代码使用了双指针技术。指针 l 从数组的左端开始，指针 r 从右端开始。在 while 循环的每一次迭代中，l 和 r 两个指针中至少有一个会向中间移动（l++ 或 r--）。指针 l 只会增加，指针 r 只会减少，它们永远不会回溯。当 l 追上或超过 r 时，循环结束。在整个过程中，两个指针共同走过的总距离最多是数组的长度 $n$。因此，循环的执行次数是线性的，时间复杂度为 $O(n)$。

答案：$O(n)$

题目 15

题意概括：分析一个与字符串处理相关的循环。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void f(string s) {
    int n = s.length();
    for (int i = 0; i < n; i++) {
        string sub = s.substr(0, i);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // ...
    return 0;
}

分析： 这个问题有一个陷阱。for 循环本身执行了 $n$ 次，其中 $n$ 是字符串 s 的长度。然而，循环体内部的 s.substr(0, i) 操作并不是 $O(1)$ 的。创建一个长度为 $i$ 的子字符串通常需要 $O(i)$ 的时间，因为它需要复制 $i$ 个字符。

因此，总的操作次数是：

$$\sum_{i=0}^{n-1} O(i) = O(0 + 1 + 2 + \dots + n-1) = O\left(\frac{(n-1)n}{2}\right) = O(n^2) $$

所以，整个函数的时间复杂度是 $O(n^2)$。

答案：$O(n^2)$

题目 16

题意概括：下面是一个使用递归计算斐波那契数列的函数。请分析其时间复杂度。

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

分析： 该函数的递归关系式为 $T(n) = T(n-1) + T(n-2) + O(1)$。这个递推关系与斐波那契数列本身的定义非常相似。其解的增长率是指数级别的，与黄金分割比 $\phi = \frac{1+\sqrt{5}}{2}$ 的幂次方有关。$T(n)$ 大致与 $\phi^n$ 成正比。因此，时间复杂度约为 $O(1.618^n)$，这是一个指数级的复杂度。我们通常记为 $O(2^n)$，因为它与 $O(2^n)$ 属于同一量级。

时间复杂度：_________

答案：$O(2^n)$

题目 17

题意概括：下面的代码段对一个大小为 $n$ 的数组进行操作。请分析其时间复杂度。

void f(int n) {
    for (int i = 0; i < n; i++) {
        // O(1) 操作
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // O(1) 操作
        }
    }
}

分析： 这个函数包含两个独立的循环块。 第一个循环是一个单层循环，执行 $n$ 次，其时间复杂度为 $O(n)$。 第二个循环是一个嵌套循环，内外层都执行 $n$ 次，其时间复杂度为 $O(n^2)$。 根据加法原则，总的时间复杂度由最高阶的项决定。 $T(n) = O(n) + O(n^2) = O(n^2)$。

时间复杂度：_________

答案：$O(n^2)$

题目 18

题意概括：下面是一个主定理（Master Theorem）的应用场景。一个递归算法的递推关系是 $T(n) = 2T(n/2) + O(n)$。请问它的时间复杂度是多少？

分析： 主定理是分析分治算法时间复杂度的强大工具。其一般形式为 $T(n) = aT(n/b) + f(n)$。 在本题中，$a=2$, $b=2$, $f(n) = O(n)$。 我们需要比较 $f(n)$ 和 $n^{\log_b a}$。 $n^{\log_b a} = n^{\log_2 2} = n^1 = n$。 我们发现 $f(n) = \Theta(n^{\log_b a})$ (即 $O(n)$)。这符合主定理的第二种情况。 根据主定理，当 $f(n) = \Theta(n^{\log_b a})$ 时，解为 $T(n) = \Theta(n^{\log_b a} \log n)$。 因此，时间复杂度为 $\Theta(n \log n)$。这正是归并排序等经典分治算法的复杂度。

时间复杂度：_________

答案：$O(n \log n)$

题目 19

题意概括：分析以下循环的时间复杂度。

void f(int n) {
    for (int i = 1; i <= n; i = i * 3) {
        for (int j = 1; j <= n; j++) {
            // O(1) 操作
        }
    }
}

分析： 这是一个嵌套循环。 外层循环的变量 i 以乘法方式增长：1, 3, 9, 27, ... 即 $3^k$。循环条件是 $3^k \le n$，解得 $k \le \log_3 n$。所以外层循环执行 $O(\log n)$ 次。 内层循环是一个简单的线性循环，执行 $n$ 次。 根据乘法原则，总的时间复杂度是外层循环次数乘以内层循环次数。 $T(n) = O(\log n) \times O(n) = O(n \log n)$。

时间复杂度：_________

答案：$O(n \log n)$

题目 20

题意概括：分析一个递减到根号的递归函数。

int f(int n) {
    if (n <= 2) {
        return 1;
    }
    return f(sqrt(n));
}

分析： 这是一个非常规的递归。我们来追踪参数 $n$ 的变化： $n \rightarrow n^{1/2} \rightarrow (n^{1/2})^{1/2} = n^{1/4} \rightarrow n^{1/8} \rightarrow \dots$ 假设递归调用了 $k$ 次，第 $k$ 次调用的参数是 $n^{(1/2)^k}$。 递归的终止条件是参数小于等于 2。所以我们要求解 $n^{(1/2)^k} \le 2$。 对不等式两边取两次对数（以2为底）： $\log_2(n^{(1/2)^k}) \le \log_2 2$ $(1/2)^k \log_2 n \le 1$ $2^k \ge \log_2 n$ $k \ge \log_2(\log_2 n)$ 因此，递归的深度是 $O(\log \log n)$。由于每次递归调用的额外开销是 $O(1)$，总的时间复杂度就是 $O(\log \log n)$。

时间复杂度：_________

答案：$O(\log \log n)$