时间复杂度与空间复杂度：从执行次数到渐进分析

Lichermione2026-08-212026-08-21

分析算法时，我们通常不关心某台机器上恰好运行了多少毫秒，而关心输入规模增长后，时间和额外空间会按什么速度增长。渐进复杂度帮助我们忽略机器、编译器和常数差异，比较算法的可扩展性。

1. 为什么不用秒表代替复杂度分析

实测时间会受到 CPU、编译器优化、缓存、操作系统负载和测试数据分布影响。同一个算法换一台机器，绝对时间可能完全不同；但当输入规模从 $n$ 扩大到 $10n$ 时，增长趋势通常仍由算法结构决定。

因此应把两种方法结合起来：

渐进分析回答规模增长时的趋势；
基准测试验证真实常数、缓存行为和具体数据分布下的表现。

2. 输入规模与基本操作

设输入规模为 $n$，选取能代表主要成本的基本操作，并统计执行次数 $T(n)$。

long long sum_array(const int a[], size_t n)
{
    long long sum = 0;
    for (size_t i = 0; i < n; ++i) {
        sum += a[i];
    }
    return sum;
}

加法执行 $n$ 次，循环判断约执行 $n+1$ 次。无论精确表达式是 $2n+3$ 还是 $4n+1$，增长速度都与 $n$ 同阶，因此时间复杂度为 $\Theta(n)$。

3. $O$、$\Omega$ 与 $\Theta$

三种记号表达的含义不同：

记号	含义	直观理解
$O(g(n))$	渐进上界	增长得不比 $g(n)$ 更快
$\Omega(g(n))$	渐进下界	增长得不比 $g(n)$ 更慢
$\Theta(g(n))$	紧确界	与 $g(n)$ 同阶增长

如果 $T(n)=3n^2+5n+8$，那么它既是 $O(n^2)$，也是 $O(n^3)$；但最有信息量的表达是 $\Theta(n^2)$。日常工程中常把 Big-O 口语化地当作“复杂度”，但严谨分析时应区分上界和紧确界。

4. 推导渐进复杂度

常用规则如下：

忽略常数项：$n+100 \rightarrow n$；
忽略低阶项：$n^2+n \rightarrow n^2$；
忽略最高阶项的常数系数：$3n^2 \rightarrow n^2$；
顺序执行的代码成本相加，保留增长最快的一项；
嵌套循环的迭代次数通常相乘，但应以实际循环边界为准。

常见增长级别从快到慢可扩展性依次为：

$$
O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)
$$

5. 循环复杂度

5.1 单层循环

1
2
3

for (size_t i = 0; i < n; ++i) {
    /* O(1) 操作 */
}

循环执行 $n$ 次，总时间为 $\Theta(n)$。

5.2 等差变化的嵌套循环

for (size_t i = 0; i < n; ++i) {
    for (size_t j = i + 1; j < n; ++j) {
        /* O(1) 操作 */
    }
}

内层执行次数为：

$$
(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}
$$

因此总时间为 $\Theta(n^2)$，不是简单看到“两层循环”后猜测，而是由总迭代次数推导出来。

5.3 倍增循环

1
2
3

for (size_t i = 1; i < n; i *= 2) {
    /* O(1) 操作 */
}

执行 $k$ 次后 $i=2^k$，当 $2^k \ge n$ 时结束，所以 $k=\lceil\log_2n\rceil$，复杂度为 $\Theta(\log n)$。

6. 最好、平均与最坏情况

在线性查找中：

目标位于第一个位置：最好时间 $\Theta(1)$；
目标位置均匀分布：平均时间 $\Theta(n)$；
目标不存在或位于末尾：最坏时间 $\Theta(n)$。

谈论复杂度时应注明是哪一种情况。工程上常关注最坏情况，因为它给出响应时间上界；但哈希表等结构也经常使用平均或期望复杂度。

7. 二分查找：$O(\log n)$ 的来源

二分查找要求数据已经有序。每比较一次，候选区间缩小一半：

#include <stddef.h>

int binary_search(const int a[], size_t n, int target)
{
    size_t left = 0;
    size_t right = n; /* 搜索区间 [left, right) */

    while (left < right) {
        size_t mid = left + (right - left) / 2;
        if (a[mid] < target) {
            left = mid + 1;
        } else if (a[mid] > target) {
            right = mid;
        } else {
            return (int)mid;
        }
    }
    return -1;
}

经过 $k$ 次迭代后，区间规模约为 $n/2^k$。令其缩小到 1，可得 $k\approx\log_2n$，所以最坏时间复杂度为 $O(\log n)$，额外空间为 $O(1)$。

注意：如果为了使用二分查找而先对一次性数据排序，总成本还要加上排序的 $O(n\log n)$。

8. 递归复杂度

8.1 线性递归

unsigned long long factorial(unsigned int n)
{
    return n < 2U ? 1ULL : n * factorial(n - 1U);
}

递推式为 $T(n)=T(n-1)+O(1)$，时间复杂度为 $O(n)$。递归深度为 $n$，每层栈帧占常数空间，因此额外空间为 $O(n)$。

8.2 朴素斐波那契

unsigned long long fibonacci(unsigned int n)
{
    return n < 2U ? n : fibonacci(n - 1U) + fibonacci(n - 2U);
}

递归树中存在大量重复计算，时间复杂度为指数级，常写作 $O(2^n)$；更紧的界是 $\Theta(\varphi^n)$，其中 $\varphi$ 是黄金分割比。递归同时存活的最大调用链长度为 $n$，所以空间复杂度是 $O(n)$，而不是把所有递归节点数量都算成同时占用的空间。

改用动态规划或迭代，可以把时间降为 $O(n)$、额外空间降为 $O(1)$。

9. 分治递推式

归并排序满足：

$$
T(n)=2T(n/2)+\Theta(n)
$$

递归树有 $\log n$ 层，每层合并的总工作量都是 $\Theta(n)$，因此总时间为 $\Theta(n\log n)$。

常见的主定理形式为：

$$
T(n)=aT(n/b)+f(n)
$$

比较 $f(n)$ 与 $n^{\log_ba}$ 的增长速度，可以覆盖许多均匀分治算法。主定理并不适用于所有递推式，例如子问题规模不等或递归项形式不规则时，需要使用递归树、代入法等其他方法。

10. 空间复杂度算什么

空间复杂度通常关注算法除输入数据外使用的额外空间峰值，包括：

局部变量与辅助数组；
动态分配的内存；
递归调用栈；
为算法维护的栈、队列、哈希表等结构。

常数个变量仍为 $O(1)$；长度为 $n$ 的辅助数组为 $O(n)$。循环执行 $n$ 次但每轮复用同一个局部变量，空间仍是 $O(1)$，因为空间复杂度看同时存在的峰值，而不是累计申请次数。

11. 均摊复杂度

动态数组大多数尾插只写一个元素，成本为 $O(1)$；容量不足时却要申请更大空间并搬移已有元素，单次成本为 $O(n)$。如果容量按常数倍增长，连续 $n$ 次尾插的总搬移量形成几何级数：

$$
1+2+4+\cdots < 2n
$$

所以 $n$ 次插入总成本为 $O(n)$，每次插入的均摊复杂度为 $O(1)$。均摊分析不是概率分析，也不表示每一次操作都是常数时间。

12. 常见误区

常数再大仍是 $O(1)$，但这不代表实际一定更快；
两层循环不一定是 $O(n^2)$，循环边界可能是 $\log n$ 或相互依赖；
$O(n)$ 不代表准确执行 $n$ 次；
递归算法的空间复杂度取决于最大同时调用深度；
只写“快速排序是 $O(n\log n)$”不完整，它的最坏时间是 $O(n^2)$；
空间并没有因为硬件变大而失去重要性，缓存、内存上限、嵌入式设备和并发服务都对空间十分敏感。

13. 分析清单

面对一段代码，可以按以下顺序分析：

明确输入规模是什么；
选择基本操作；
写出循环次数或递推式；
区分最好、平均、最坏或均摊情况；
给出渐进上界，必要时给出紧确界；
统计额外内存峰值和递归深度；
最后再用真实数据做基准测试。

复杂度不是为代码贴一个标签，而是解释算法随规模增长时会发生什么。把假设和边界写清楚，结论才真正有用。