Hello 算法：时间复杂度分析全解——从大 O 记号推算到算法效率判断

本文基于 Hello 算法（hello-algo）教程中的「时间复杂度」章节展开，完整继承原文档的统计思路、大 $O$ 记号定义、两步推算方法与常见复杂度类型，并结合仓库中 Python 示例源码 与 C++ 示例源码 给出可一键运行的实践路径。读完后你将掌握：为什么不能直接统计算法运行时间、如何从代码推算大 $O$ 复杂度、七种常见复杂度类型的代码特征，以及最差/最佳/平均三种复杂度指标（$O$、$\Omega$、$\Theta$）的适用场景。

为什么不能直接统计算法运行时间

运行时间可以直观且准确地反映算法的效率。如果想准确预估一段代码的运行时间，理论上需要三步：

1. 确定运行平台，包括硬件配置、编程语言、系统环境等，这些因素都会影响代码的运行效率；
2. 评估各种计算操作所需的运行时间，例如加法操作 + 需要 1 ns，乘法操作 * 需要 10 ns，打印操作 print() 需要 5 ns 等；
3. 统计代码中所有的计算操作，并将所有操作的执行时间求和，从而得到运行时间。

以如下代码为例，输入数据大小为 $n$（教程同时提供了 Python、C++、Java、C#、Go、Swift、JavaScript、TypeScript、Dart、Rust、C、Kotlin、Ruby 共十余种语言版本，这里以 Python 为例）：

# 在某运行平台下
def algorithm(n: int):
    a = 2      # 1 ns
    a = a + 1  # 1 ns
    a = a * 2  # 10 ns
    # 循环 n 次
    for _ in range(n):  # 1 ns
        print(0)        # 5 ns

按上述方法可以得到该算法的运行时间为 $(6n + 12)$ ns：

$$1 + 1 + 10 + (1 + 5) \times n = 6n + 12$$

但实际上，统计算法的运行时间既不合理也不现实：一方面，我们不希望将预估时间和运行平台绑定，因为算法需要在各种不同的平台上运行；另一方面，我们很难获知每种操作的运行时间，这给预估过程带来了极大的难度。这正是「时间复杂度」这一抽象概念存在的根本原因。

时间增长趋势：常数阶、线性阶与「大常数」陷阱

时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。假设输入数据大小为 $n$，给定三个算法 A、B 和 C：

# 算法 A 的时间复杂度：常数阶
def algorithm_A(n: int):
    print(0)

# 算法 B 的时间复杂度：线性阶
def algorithm_B(n: int):
    for _ in range(n):
        print(0)

# 算法 C 的时间复杂度：常数阶
def algorithm_C(n: int):
    for _ in range(1000000):
        print(0)

• 算法 A 只有 1 个打印操作，运行时间不随着 $n$ 增大而增长，称为「常数阶」；
• 算法 B 中的打印操作需要循环 $n$ 次，运行时间随 $n$ 增大呈线性增长，称为「线性阶」；
• 算法 C 需要循环 1000000 次，虽然运行时间很长，但它与输入数据大小 $n$ 无关，因此 C 的时间复杂度和 A 相同，仍为「常数阶」。

相较于直接统计算法运行时间，时间复杂度分析有三个显著特点：

• 能有效评估算法效率。例如算法 B 的运行时间呈线性增长，在 $n > 1$ 时比算法 A 更慢，在 $n > 1000000$ 时比算法 C 更慢。事实上，只要输入数据大小 $n$ 足够大，复杂度为「常数阶」的算法一定优于「线性阶」的算法，这正是时间增长趋势的含义。
• 推算方法更简便。运行平台和计算操作类型都与运行时间的增长趋势无关，因此可以把所有计算操作的执行时间视为相同的「单位时间」，将「计算操作运行时间统计」简化为「计算操作数量统计」，估算难度大大降低。
• 存在一定局限性。尽管算法 A 和 C 的时间复杂度相同，但实际运行时间差别很大；同样，尽管算法 B 的时间复杂度比 C 高，但在 $n$ 较小时 B 明显优于 C。对于此类情况，难以仅凭时间复杂度判断算法效率的高低。当然，复杂度分析仍然是评判算法效率最有效且常用的方法。

渐近上界：大 O 记号的数学定义

给定一个输入大小为 $n$ 的函数：

def algorithm(n: int):
    a = 1      # +1
    a = a + 1  # +1
    a = a * 2  # +1
    # 循环 n 次
    for i in range(n):  # +1
        print(0)        # +1

设算法的操作数量是输入数据大小 $n$ 的函数，记为 $T(n)$，则以上函数的操作数量为：

$$T(n) = 3 + 2n$$

$T(n)$ 是一次函数，说明其运行时间的增长趋势是线性的，因此它的时间复杂度是线性阶，记为 $O(n)$。这个数学符号称为大 $O$ 记号（big-$O$ notation），表示函数 $T(n)$ 的渐近上界（asymptotic upper bound）。

函数渐近上界：若存在正实数 $c$ 和实数 $n_0$，使得对于所有的 $n > n_0$，均有 $T(n) \leq c \cdot f(n)$，则可认为 $f(n)$ 给出了 $T(n)$ 的一个渐近上界，记为 $T(n) = O(f(n))$。

计算渐近上界，就是寻找一个函数 $f(n)$，使得当 $n$ 趋向于无穷大时，$T(n)$ 和 $f(n)$ 处于相同的增长级别，仅相差一个常数系数 $c$。时间复杂度分析本质上就是计算「操作数量 $T(n)$」的渐近上界，它具有明确的数学定义。

推算方法：两步走

第一步：统计操作数量

针对代码，逐行从上到下计算即可。由于定义中 $c \cdot f(n)$ 里的常数系数 $c$ 可以取任意大小，因此操作数量 $T(n)$ 中的各种系数、常数项都可以忽略。由此总结出三条计数简化技巧：

1. 忽略 $T(n)$ 中的常数，因为它们都与 $n$ 无关，对时间复杂度不产生影响；
2. 省略所有系数。例如循环 $2n$ 次、$5n + 1$ 次等，都可以简化记为 $n$ 次，因为 $n$ 前面的系数对时间复杂度没有影响；
3. 循环嵌套时使用乘法。总操作数量等于外层循环和内层循环操作数量之积，每一层循环依然可以分别套用第 1、2 条技巧。

给定如下函数，用上述技巧统计操作数量：

def algorithm(n: int):
    a = 1      # +0（技巧 1）
    a = a + n  # +0（技巧 1）
    # +n（技巧 2）
    for i in range(5 * n + 1):
        print(0)
    # +n*n（技巧 3）
    for i in range(2 * n):
        for j in range(n + 1):
            print(0)

完整统计与「偷懒」统计的结果对比如下，两者推算出的时间复杂度都为 $O(n^2)$：

$$\begin{aligned} T(n) & = 2n(n + 1) + (5n + 1) + 2 & \text{完整统计} \\ & = 2n^2 + 7n + 3 \\ T(n) & = n^2 + n & \text{偷懒统计} \end{aligned}$$

第二步：判断渐近上界

时间复杂度由 $T(n)$ 中最高阶的项来决定。这是因为在 $n$ 趋于无穷大时，最高阶的项将发挥主导作用，其他项的影响都可以忽略。下表展示了一些例子，其中一些夸张的值是为了强调「系数无法撼动阶数」这一结论——当 $n$ 趋于无穷大时，这些常数变得无足轻重：

操作数量 $T(n)$	时间复杂度 $O(f(n))$
$100000$	$O(1)$
$3n + 2$	$O(n)$
$2n^2 + 3n + 2$	$O(n^2)$
$n^3 + 10000n^2$	$O(n^3)$
$2^n + 10000n^{10000}$	$O(2^n)$

常见复杂度类型：结合仓库源码逐一拆解

设输入数据大小为 $n$，常见的时间复杂度类型按从低到高的顺序排列为：

$$\begin{aligned} & O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!) \\ & \text{常数阶} < \text{对数阶} < \text{线性阶} < \text{线性对数阶} < \text{平方阶} < \text{指数阶} < \text{阶乘阶} \end{aligned}$$

仓库中 codes/python/chapter_computational_complexity/time_complexity.py 为每种复杂度类型都提供了可运行的示例函数，函数返回对应的操作数量 count，可以直接修改 n 运行来体会各复杂度的操作数量变化趋势（同构实现还存在于 codes/java、codes/cpp、codes/javascript、codes/go、codes/rust 等十余个语言目录下）。

常数阶 $O(1)$

常数阶的操作数量与输入数据大小 $n$ 无关。以下函数中，尽管操作数量 size 可能很大，但由于其与 $n$ 无关，时间复杂度仍为 $O(1)$（源码见 constant）：

def constant(n: int) -> int:
    """常数阶"""
    count = 0
    size = 100000
    for _ in range(size):
        count += 1
    return count

这恰好呼应了前文算法 C 的结论：循环一百万次依然是常数阶。

线性阶 $O(n)$

线性阶的操作数量相对于 $n$ 以线性级别增长，通常出现在单层循环中（源码见 linear）：

def linear(n: int) -> int:
    """线性阶"""
    count = 0
    for _ in range(n):
        count += 1
    return count

遍历数组、遍历链表等操作的时间复杂度均为 $O(n)$，其中 $n$ 为数组或链表的长度：

def array_traversal(nums: list[int]) -> int:
    """线性阶（遍历数组）"""
    count = 0
    # 循环次数与数组长度成正比
    for num in nums:
        count += 1
    return count

值得注意的是，输入数据大小 $n$ 需根据输入数据的类型来具体确定。比如在第一个示例中，变量 $n$ 为输入数据大小；在第二个示例中，数组长度 $n$ 才是数据大小。

平方阶 $O(n^2)$

平方阶的操作数量相对于 $n$ 以平方级别增长，通常出现在嵌套循环中：外层循环和内层循环的时间复杂度都为 $O(n)$，因此总体时间复杂度为 $O(n^2)$（源码见 quadratic）：

def quadratic(n: int) -> int:
    """平方阶"""
    count = 0
    # 循环次数与数据大小 n 成平方关系
    for i in range(n):
        for j in range(n):
            count += 1
    return count

以冒泡排序为例（源码见 bubble_sort），外层循环执行 $n - 1$ 次，内层循环执行 $n-1$、$n-2$、$\dots$、$2$、$1$ 次，平均为 $n/2$ 次，因此时间复杂度为 $O((n - 1) n / 2) = O(n^2)$：

def bubble_sort(nums: list[int]) -> int:
    """平方阶（冒泡排序）"""
    count = 0  # 计数器
    # 外循环：未排序区间为 [0, i]
    for i in range(len(nums) - 1, 0, -1):
        # 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for j in range(i):
            if nums[j] > nums[j + 1]:
                # 交换 nums[j] 与 nums[j + 1]
                tmp: int = nums[j]
                nums[j] = nums[j + 1]
                nums[j + 1] = tmp
                count += 3  # 元素交换包含 3 个单元操作
    return count

从源码结构看，示例中的计数器 count += 3 把一次「三变量交换」拆成 3 个单元操作来累计，这正是「将所有操作视为单位时间、只统计操作数量」这一简化思想在代码中的具体落地。

指数阶 $O(2^n)$

生物学的「细胞分裂」是指数阶增长的典型例子：初始状态为 1 个细胞，分裂一轮后变为 2 个，两轮后变为 4 个，分裂 $n$ 轮后有 $2^n$ 个细胞。以下代码模拟了该过程（源码见 exponential），输入 $n$ 表示分裂轮数，返回值 count 表示总分裂次数：

def exponential(n: int) -> int:
    """指数阶（循环实现）"""
    count = 0
    base = 1
    # 细胞每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
    for _ in range(n):
        for _ in range(base):
            count += 1
        base *= 2
    # count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
    return count

从源码中的注释可以直接读出结论：count = 1 + 2 + 4 + 8 + ... + 2^(n-1) = 2^n - 1，即等比数列求和，时间复杂度为 $O(2^n)$。

在实际算法中，指数阶常出现于递归函数中。例如以下代码递归地一分为二，经过 $n$ 次分裂后停止（源码见 exp_recur）：

def exp_recur(n: int) -> int:
    """指数阶（递归实现）"""
    if n == 1:
        return 1
    return exp_recur(n - 1) + exp_recur(n - 1) + 1

指数阶增长非常迅速，在穷举法（暴力搜索、回溯等）中比较常见。对于数据规模较大的问题，指数阶是不可接受的，通常需要使用动态规划或贪心算法等来解决。

对数阶 $O(\log n)$

与指数阶相反，对数阶反映了「每轮缩减到一半」的情况。由于每轮缩减到一半，循环次数是 ${}_{2}n$，即 $2^n$ 的反函数。以下代码模拟了该过程，时间复杂度为 $O({}_{2}n)$，简记为 $O(\log n)$（源码见 logarithmic）：

def logarithmic(n: int) -> int:
    """对数阶（循环实现）"""
    count = 0
    while n > 1:
        n = n / 2
        count += 1
    return count

与指数阶类似，对数阶也常出现于递归函数中。以下代码形成了一棵高度为 ${}_{2}n$ 的递归树（源码见 log_recur）：

def log_recur(n: int) -> int:
    """对数阶（递归实现）"""
    if n <= 1:
        return 0
    return log_recur(n / 2) + 1

对数阶常出现于基于分治策略的算法中，体现了「一分为多」和「化繁为简」的算法思想。它增长缓慢，是仅次于常数阶的理想时间复杂度。

$O(\log n)$ 的底数是多少？ 准确来说，「一分为 $m$」对应的时间复杂度是 $O(\log_m n)$。而通过对数换底公式，可以得到具有不同底数、相等的时间复杂度：

$$O(\log_m n) = O(\log_k n / \log_k m) = O(\log_k n)$$

也就是说，底数 $m$ 可以在不影响复杂度的前提下转换，因此通常会省略底数，将对数阶直接记为 $O(\log n)$。

线性对数阶 $O(n \log n)$

线性对数阶常出现于嵌套循环中，两层循环的时间复杂度分别为 $O(\log n)$ 和 $O(n)$。仓库中采用递归方式构造了这样的操作结构（源码见 linear_log_recur）：

def linear_log_recur(n: int) -> int:
    """线性对数阶"""
    if n <= 1:
        return 1
    # 一分为二，子问题的规模减小一半
    count = linear_log_recur(n // 2) + linear_log_recur(n // 2)
    # 当前子问题包含 n 个操作
    for _ in range(n):
        count += 1
    return count

从源码结构看，该函数构成一棵二叉递归树：每一层的操作总数都为 $n$（即该层的 for _ in range(n)），而树共有 $\log_2 n + 1$ 层（每往下一层，子问题规模减半），因此时间复杂度为 $O(n \log n)$。

主流排序算法的时间复杂度通常为 $O(n \log n)$，例如快速排序、归并排序、堆排序等。

阶乘阶 $O(n!)$

阶乘阶对应数学上的「全排列」问题。给定 $n$ 个互不重复的元素，求其所有可能的排列方案，方案数量为：

$$n! = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1$$

阶乘通常使用递归实现。第一层分裂出 $n$ 个，第二层分裂出 $n-1$ 个，以此类推，直至第 $n$ 层时停止分裂（源码见 factorial_recur）：

def factorial_recur(n: int) -> int:
    """阶乘阶（递归实现）"""
    if n == 0:
        return 1
    count = 0
    # 从 1 个分裂出 n 个
    for _ in range(n):
        count += factorial_recur(n - 1)
    return count

请注意，因为当 $n \geq 4$ 时恒有 $n! > 2^n$，所以阶乘阶比指数阶增长得更快，在 $n$ 较大时也是不可接受的。

最差、最佳、平均时间复杂度

算法的时间效率往往不是固定的，而是与输入数据的分布有关。假设输入一个长度为 $n$ 的数组 nums，其中 nums 由从 1 至 $n$ 的数字组成，每个数字只出现一次；但元素顺序是随机打乱的，任务目标是返回元素 1 的索引。可以得出以下结论：

• 当 nums = [?, ?, ..., 1]，即末尾元素是 1 时，需要完整遍历数组，达到最差时间复杂度 $O(n)$；
• 当 nums = [1, ?, ?, ...]，即首个元素为 1 时，无论数组多长都不需要继续遍历，达到最佳时间复杂度 $\Omega(1)$。

「最差时间复杂度」对应函数渐近上界，使用大 $O$ 记号表示；「最佳时间复杂度」对应函数渐近下界，用 $\mathrm{\Omega }$ 记号表示。仓库中 worst_best_time_complexity.py 完整实现了这一示例：

def random_numbers(n: int) -> list[int]:
    """生成一个数组，元素为: 1, 2, ..., n ，顺序被打乱"""
    # 生成数组 nums =: 1, 2, 3, ..., n
    nums = [i for i in range(1, n + 1)]
    # 随机打乱数组元素
    random.shuffle(nums)
    return nums

def find_one(nums: list[int]) -> int:
    """查找数组 nums 中数字 1 所在索引"""
    for i in range(len(nums)):
        # 当元素 1 在数组头部时，达到最佳时间复杂度 O(1)
        # 当元素 1 在数组尾部时，达到最差时间复杂度 O(n)
        if nums[i] == 1:
            return i
    return -1

其驱动代码 main 部分 会随机打乱 100 个数字并反复调用 find_one，运行即可直观看到：数字 1 落在不同索引时，循环次数在 1 到 $n$ 之间浮动。

值得说明的是，实际中很少使用最佳时间复杂度，因为它通常只有在很小概率下才能达到，可能带来误导性。而最差时间复杂度更为实用，因为它给出了一个效率安全值，让我们可以放心地使用算法。

从上述示例可以看出，最差时间复杂度和最佳时间复杂度只出现于「特殊的数据分布」，出现概率可能很小，并不能真实反映算法运行效率。相比之下，平均时间复杂度可以体现算法在随机输入数据下的运行效率，用 $\Theta$ 记号表示。

对于部分算法，可以简单地推算出随机数据分布下的平均情况。比如上述示例：输入数组被打乱后，元素 1 出现在任意索引的概率都相等，那么算法的平均循环次数就是数组长度的一半 $n/2$，平均时间复杂度为 $\Theta(n / 2) = \Theta(n)$。

但对于较为复杂的算法，计算平均时间复杂度往往比较困难，因为很难分析出数据分布下的整体数学期望。在这种情况下，通常使用最差时间复杂度作为算法效率的评判标准。

为什么很少看到 $\Theta$ 符号？ 可能由于 $O$ 符号过于朗朗上口，因此人们常常使用它来表示平均时间复杂度。但从严格意义上讲，这种做法并不规范。若遇到「平均时间复杂度 $O(n)$」的表述，请将其直接理解为 $\Theta(n)$。

动手实践：一键运行仓库中的复杂度示例

上述所有示例代码均可在本地直接运行验证。以 Python 为例：

python codes/python/chapter_computational_complexity/time_complexity.py

脚本的 Driver Code 会依次调用 constant、linear、array_traversal、quadratic、bubble_sort、exponential、exp_recur、logarithmic、log_recur、linear_log_recur、factorial_recur，并打印每个函数在给定 $n$ 下的操作数量。源码注释明确提示「可以修改 n 运行，体会一下各种复杂度的操作数量变化趋势」——将 n 从 8 逐步增大，可以直观观察到：常数阶的 count 恒为 100000；线性阶线性增长；平方阶加速增长；而指数阶与阶乘阶的 count 会随 n 迅速膨胀。

C++ 版本 codes/cpp/chapter_computational_complexity/time_complexity.cpp 提供了同构的 main 函数，且各语言目录（codes/java、codes/c、codes/go、codes/rust、codes/javascript、codes/typescript 等）均按相同的章节结构组织，方便用你最熟悉的语言对照阅读与运行。本章内容对应教程中的 复杂度分析章节，配套的 空间复杂度 与 迭代与递归 文档可作为延伸阅读。