Hello 算法（hello-algo）时间复杂度精讲：从逐行统计到大 O 渐近分析的完整实战指南

2026-09-06 18:31:06作者：韦蓉瑛

导读

本文以《Hello 算法》（hello-algo）仓库英文版教程 time_complexity.md 为骨架，系统讲解时间复杂度分析的全过程：为什么直接测量运行时间不可行、如何用大 O 记号刻画算法运行时间的增长趋势、如何按"两步法"推导渐近上界，以及常数阶、线性阶、平方阶、指数阶、对数阶、线性对数阶、阶乘阶等常见复杂度类型的特征与典型代码形态。文中所有示例函数均可在仓库的 time_complexity.py、time_complexity.cpp 等 14 种语言的同名源码文件中找到一一对应的实现，读者可亲手运行观察操作数量随数据规模变化的趋势。

为什么不能靠"数运行时间"来评估算法

运行时间可以直观、准确地反映算法的效率。如果想精确估算一段代码的运行时间，教科书式的做法分为三步：

确定运行平台：硬件配置、编程语言、系统环境等都会影响代码执行效率；
评估各类计算操作的耗时：例如一次加法 + 约 1 ns、一次乘法 * 约 10 ns、一次打印 print() 约 5 ns；
统计代码中的所有计算操作，把各操作耗时累加得到总运行时间。

以 time_complexity.md 中给出的多语言示例函数（输入数据规模为 $n$ ）为例，Python 版本可写为：

# On a certain running platform
def algorithm(n: int):
    a = 2      # 1 ns
    a = a + 1  # 1 ns
    a = a * 2  # 10 ns
    # Loop n times
    for _ in range(n):  # 1 ns
        print(0)        # 5 ns

按照上述假设的耗时，可列出算式：

1 + 1 + 10 + (1 + 5) \times n = 6n + 12 \ \text{ns}

然而，原文档明确指出：试图统计算法的精确运行时间既不实用也不现实，原因有三：

我们不希望把估算结果绑定到某个运行平台，因为算法需要在众多不同的平台上运行；
很难精确获知每一种操作的真实耗时，导致估算过程极其困难；
即便算出一个带单位的结果，它也只对特定环境成立，无法在不同环境间迁移比较。

仓库中关于"算法效率评估"的另一篇前置文档 performance_evaluation.md 从更宏观的角度补充了背景：效率评估分为"实际测试"与"理论估算"两类，实际测试受测试环境干扰难以消除、且全规模测试资源消耗大；而渐近复杂度分析无需真实运行代码、独立于测试环境、并能反映算法在大数据量下的表现。时间复杂度分析正是理论估算的核心工具。

从"统计运行时间"转向"统计增长趋势"

时间复杂度分析统计的不是算法的运行时间，而是算法运行时间随数据量增大而增长的趋势。理解"时间增长趋势"这个概念可借助三个算法 A、B、C（输入数据规模为 $n$ ）：

=== "Python"

```python title=""
# Time complexity of algorithm A: constant order
def algorithm_A(n: int):
    print(0)
# Time complexity of algorithm B: linear order
def algorithm_B(n: int):
    for _ in range(n):
        print(0)
# Time complexity of algorithm C: constant order
def algorithm_C(n: int):
    for _ in range(1000000):
        print(0)
```

三者的复杂度判读如下：

算法 A 只有 1 次打印操作，运行时间不随 $n$ 增长，称为常数阶（constant order）；
算法 B 的打印操作需要循环 $n$ 次，运行时间随 $n$ 线性增长，称为线性阶（linear order）；
算法 C 的打印操作需要循环 $1000000$ 次，虽然运行时间很长，但与输入规模 $n$ 无关，因此与 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
    # Loop n times
    for i in range(n):  # +1
        print(0)        # +1

记操作次数为 $T (n)$ ，则有：

T (n) = 3 + 2 n

$T (n)$ 是一次线性函数，说明运行时间的增长趋势是线性的，因此时间复杂度为线性阶。线性阶记作 $O (n)$ ，这里的符号称为大 $O$ 记号（big- $O$ notation），表示函数 $T (n)$ 的渐近上界（asymptotic upper bound）。时间复杂度分析本质上就是在计算"操作数量 $T (n)$ "的渐近上界。

其严格数学定义为：

!!! note "函数的渐近上界"

若存在正实数 $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) = 3 + 2 n$ 即满足 $3 + 2n \leq 3n$ （取 $c = 3$ ， $n_{0} = 3$ 即可验证），故其渐近上界为 $O (n)$ 。

两步推导法：统计操作数量 → 确定渐近上界

渐近上界的思路偏数学化，若一时难以理解可先掌握推导方法，再通过持续练习体会其数学含义。确定 $f (n)$ 总体分为两步。

Step 1：统计操作数量

对代码自上而下、逐行统计即可。但由于 $c \cdot f(n)$ 中的常数系数 $c$ 可以是任意大小， $T (n)$ 中的系数与常数项都可以忽略，由此可总结三条简化技巧：

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

以文档中的综合示例（Python 版）为例：

def algorithm(n: int):
    a = 1      # +0 (Technique 1)
    a = a + n  # +0 (Technique 1)
    # +n (Technique 2)
    for i in range(5 * n + 1):
        print(0)
    # +n*n (Technique 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{完整统计} \newline & = 2n^2 + 7n + 3 \newline T(n) & = n^2 + n & \text{简化统计} \end{aligned}

Step 2：确定渐近上界

时间复杂度由 $T (n)$ 的最高阶项决定：当 $n$ 趋于无穷时，最高阶项起主导作用，其余项的影响可以忽略。下表给出若干操作数量到时间复杂度的对应示例（刻意使用夸张数值以强调"系数无法撼动阶数"）：

操作数量 $T (n)$	时间复杂度 $O (f (n))$
$100000$	$O (1)$
$3 n + 2$	$O (n)$
$2 n^{2} + 3 n + 2$	$O (n^{2})$
$n^{3} + 10000 n^{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!) \newline & \text{常数} < \text{对数} < \text{线性} < \text{线性对数} < \text{平方} < \text{指数} < \text{阶乘} \end{aligned}

常数阶 $O (1)$

常数阶的操作数量与输入数据规模 $n$ 无关，不随 $n$ 变化。下面的函数中，虽然 size 的取值可能很大，但它独立于输入规模 $n$ ，时间复杂度仍是 $O (1)$ 。对应仓库源码见 time_complexity.py 中的 constant()（C++ 版本见 time_complexity.cpp）：

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

线性阶 $O (n)$

线性阶的操作数量相对 $n$ 线性增长，通常出现在单层循环中，见 linear()（源码 time_complexity.py）。遍历数组、遍历链表等操作的时间复杂度都是 $O (n)$ ，其中 $n$ 为数组或链表的长度，对应 array_traversal()（time_complexity.py）：

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

def array_traversal(nums: list[int]) -> int:
    """Linear order (traversing array)"""
    count = 0
    for num in nums:  # Number of iterations is proportional to the array length
        count += 1
    return count

值得注意：输入数据规模 $n$ 需根据输入数据的类型来确定。前一个例子中变量 $n$ 是输入规模；后一个例子中数组长度 $n$ 才是数据规模。

平方阶 $O (n^{2})$

平方阶的操作数量相对 $n$ 呈平方级增长，通常出现在嵌套循环中：外层与内层循环的时间复杂度都是 $O (n)$ ，整体即 $O (n^{2})$ ，见 quadratic()（time_complexity.py）。

以冒泡排序为例：外层循环执行 $n - 1$ 次，内层循环分别执行 $n - 1$ 、 $n - 2$ 、 $\dots$ 、 $2$ 、 $1$ 次，平均 $n / 2$ 次，因此时间复杂度为 $O ((n - 1) n / 2) = O (n^{2})$ 。仓库中的 bubble_sort() 在每次元素交换时计入 3 次单位操作，用于量化统计（见 time_complexity.py）：

def bubble_sort(nums: list[int]) -> int:
    """Quadratic order (bubble sort)"""
    count = 0  # Counter
    # Outer loop: unsorted range is [0, i]
    for i in range(len(nums) - 1, 0, -1):
        # Inner loop: swap the largest element in the unsorted range [0, i] to the rightmost end
        for j in range(i):
            if nums[j] > nums[j + 1]:
                tmp: int = nums[j]
                nums[j] = nums[j + 1]
                nums[j + 1] = tmp
                count += 3  # Element swap includes 3 unit operations
    return count

指数阶 $O (2^{n})$

生物学中的"细胞分裂"是指数阶增长的典型例子：初始为 1 个细胞，分裂 1 轮后变为 2 个，2 轮后变为 4 个…… $n$ 轮后共有 $2^{n}$ 个细胞。仓库代码 exponential() 用双层循环模拟该过程，输入 $n$ 表示分裂轮数，返回值 count 表示分裂总次数：

def exponential(n: int) -> int:
    """Exponential order (loop implementation)"""
    count = 0
    base = 1
    # Cells divide into two every round: 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

实际算法中，指数阶常出现于递归函数。例如 exp_recur() 每次递归分裂为两个规模减半的子问题，分裂 $n$ 次后停止：

def exp_recur(n: int) -> int:
    """Exponential order (recursive implementation)"""
    if n == 1:
        return 1
    return exp_recur(n - 1) + exp_recur(n - 1) + 1

指数阶增长极快，常见于穷举法（暴力搜索、回溯等）。对于大规模问题，指数阶不可接受，通常需要借助动态规划或贪心算法求解。

对数阶 $O(\log n)$

与指数阶相反，对数阶刻画的是"每轮缩减到一半"的情形。设输入规模为 $n$ ，每轮减半则循环次数为 $\log_2 n$ ，它正是 $2^{n}$ 的反函数。仓库中的 logarithmic() 模拟"每轮缩减一半"的过程：

def logarithmic(n: int) -> int:
    """Logarithmic order (loop implementation)"""
    count = 0
    while n > 1:
        n = n / 2
        count += 1
    return count

与指数阶类似，对数阶也常出现在递归函数中，例如 log_recur() 形成的递归树高度为 $\log_2 n$ ：

def log_recur(n: int) -> int:
    """Logarithmic order (recursive implementation)"""
    if n <= 1:
        return 0
    return log_recur(n / 2) + 1

对数阶常见于基于分治策略的算法，体现"不断拆解问题、化繁为简"的思想，增长缓慢，是仅次于常数阶的理想复杂度。

!!! tip " $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()（time_complexity.py）的递归树结构是：每一层共有 $n$ 次操作，树共有 $\log_2 n + 1$ 层，因而总复杂度为 $O(n \log n)$ 。

主流的排序算法（快速排序、归并排序、堆排序等）时间复杂度通常为 $O (n \log n)$ ，相关实现可参见仓库的 chapter_sorting 目录，例如 quick_sort.py、merge_sort.py、heap_sort.py。

阶乘阶 $O (n!)$

阶乘阶对应数学中的"全排列"问题：给定 $n$ 个互不相同的元素，求所有可能的排列方案，其数量为：

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

阶乘通常用递归实现，见 factorial_recur()（time_complexity.py）：第 1 层分裂为 $n$ 个分支，第 2 层分裂为 $n - 1$ 个分支，依此类推，直到第 $n$ 层停止。

注意：由于当 $n \geq 4$ 时恒有 $n! > 2^{n}$ ，阶乘阶比指数阶增长更快，对于较大的 $n$ 同样不可接受。

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

算法的时间效率往往并非固定，而与输入数据的分布有关。假设输入一个长度为 $n$ 的数组 nums，其中元素为 $1$ 到 $n$ 的排列且顺序随机打乱，任务返回元素 $1$ 的索引。仓库中的完整可运行示例见 worst_best_time_complexity.py（random_numbers() 用于生成打乱后的数组，find_one() 用于查找）：

def find_one(nums: list[int]) -> int:
    """Find the index of number 1 in array nums"""
    for i in range(len(nums)):
        # When element 1 is at the head of the array, best time complexity O(1) is achieved
        # When element 1 is at the tail of the array, worst time complexity O(n) is achieved
        if nums[i] == 1:
            return i
    return -1

可得如下结论：

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

这里引入了三种记号：最差时间复杂度对应函数的渐近上界，用大 $O$ 记号；最佳时间复杂度对应函数的渐近下界，用 $Ω$ 记号；平均时间复杂度可反映随机输入下算法的实际运行效率，用 $Θ$ 记号。对应的 Java 等语言的示例见仓库 worst_best_time_complexity.cpp 与 worst_best_time_complexity.c。

几点实践建议与注意事项：

实践中很少使用最佳时间复杂度，因为它通常只能在极低概率下达到，且可能具有误导性；最差时间复杂度更具实用性，它给出了效率的安全值，可放心使用算法；
最差与最佳时间复杂度都只在特定的输入分布下出现，出现概率很低，未必能真实反映运行效率；
对某些算法可简单推导随机数据分布下的平均情况。如上例中数组已打乱，元素 $1$ 出现在任意索引的概率相等，因此平均循环次数为数组长度的一半 $n / 2$ ，平均时间复杂度为 $\Theta(n / 2) = \Theta(n)$ ；
对于更复杂的算法，平均时间复杂度往往难以计算（难以分析数据分布下的整体数学期望），此时通常以最差时间复杂度作为评判算法效率的标准。

!!! question "为何 $\Theta$ 符号很少见？"

可能是因为 $O$ 符号太深入人心，我们常拿它来表示平均时间复杂度。但严格来说这不规范。在本书与其他资料中，若见到"平均时间复杂度 $O(n)$"这类表述，请直接理解为 $\Theta(n)$。

结合仓库源码动手验证

仓库为上述每一类复杂度都提供了跨语言实现与可运行的驱动代码。以 Python 为例，运行 time_complexity.py：

python3 codes/python/chapter_computational_complexity/time_complexity.py

默认输入规模 $n = 8$ ，实测输出各复杂度函数的操作数量为：

输入数据大小 n = 8
常数阶的操作数量 = 100000
线性阶的操作数量 = 8
线性阶（遍历数组）的操作数量 = 8
平方阶的操作数量 = 64
平方阶（冒泡排序）的操作数量 = 84
指数阶（循环实现）的操作数量 = 255
指数阶（递归实现）的操作数量 = 255
对数阶（循环实现）的操作数量 = 3
对数阶（递归实现）的操作数量 = 3
线性对数阶（递归实现）的操作数量 = 32
阶乘阶（递归实现）的操作数量 = 40320

这些实测数字恰好印证了理论推导：常数阶不随 $n$ 变化；对数阶仅约 $_{2} 8 = 3$ 次；指数阶为 $2^{8} - 1 = 255$ ；阶乘阶为 $8! = 40320$ 。读者可修改驱动代码中的 n 值重新运行，直观观察不同复杂度操作数量的增长差异。同样的函数在仓库其他语言目录下均有完整实现，包括 C（time_complexity.c）、C++（time_complexity.cpp）、Java、Go、Rust、Swift、JavaScript、TypeScript、Dart、Kotlin、Ruby 等（见 codes/<language>/chapter_computational_complexity/），可用于跨语言对照学习。