数据结构与算法复杂度：大 O 表示法的前世今生与复杂度计算全攻略

想象这样一个场景：你买了一大箱书，随手摞在书桌上。要找一本《算法导论》，你得一本一本地翻，运气好第一本就是，运气差要翻到最底下一本。后来你把书按类别摆上书架，计算机类的放一起，文学类的放一起，再按书名首字母排好序，从此找书只需要几十秒。你看，同样是"存书"这件事，组织方式不同，后续查找的效率天差地别。

计算机里也一样。同样是存 100 万个整数，用数组存和用链表存，插入、删除、查找的性能表现完全不同；同样是给 100 万个数字排序，冒泡排序和快速排序的耗时可能是"一分钟"和"一瞬间"的差距。这就引出了计算机科学里一对最基础也最重要的概念——数据结构和算法。而衡量它们好坏的标尺，就是我们这篇文章的主角：时间复杂度与空间复杂度，以及那个让人又爱又恨的大 O 表示法。

顺便说一句，这不是考试才有的考点——几乎所有公司的校园招聘笔试和面试都会考察数据结构和算法。可以说，这是程序员的"内功心法"，也是你从"会写代码"走向"写好代码"的必经之路。

什么是数据结构

数据结构（Data Structure）是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

这句话有点绕，拆开看就清楚了。核心是三个关键词：

1. 数据元素：要存的东西。一个整数、一条订单记录，都是数据元素；
2. 关系：元素与元素之间不是孤立的。数组里元素按位置相邻，链表里元素有前驱后继，树里元素有父子关系，图里元素有任意连接关系；
3. 存储与组织方式：把这些元素按某种关系装起来的具体形态。

为什么我们不去用"一种万能结构"存所有东西？因为没有一种单一的数据结构对所有用途都有用。就像收纳盒：装袜子用分格盒，装文件用文件夹，装大衣用衣柜——各有各的适用场景。所以我们要学各式各样的数据结构：线性表（顺序表、链表）、栈、队列、二叉树、哈希表、图……每一种都是为解决某一类特定问题而生的。

什么是算法

算法（Algorithm）：定义良好的计算过程，它取一个或一组值作为输入，并产生出一个或一组值作为输出。简单来说，算法就是一系列计算步骤，用来将输入数据转化成输出结果。

最直白的理解：算法就是解决一个问题的具体步骤。比如"把数组从小到大排序"是一个问题，冒泡排序、选择排序、快速排序都是解决它的算法；"找到数组中最大的数"是一个问题，遍历一遍记录最大值就是算法。

你有没有发现，算法和数据结构是伴生的：数据结构解决"数据怎么存"，算法解决"数据怎么用"。选错了存储方式，再好的算法也跑不快；选对了存储方式，算法往往事半功倍——比如"频繁在头部插入删除"就选链表而不是数组。这也是为什么两者总是被放在一起学习。

为什么数据结构和算法如此重要

最现实的原因：校园招聘笔试必考，校园招聘面试必考。翻开任何一家大厂的笔试真题，排序、查找、链表、二叉树、动态规划几乎是标配。面试官考的不是你背没背过答案，而是你有没有建立"用数据结构组织数据、用算法解决问题"的思维方式。

更深层的原因是：它决定了一个程序员的上限。业务代码写多了你会发现，大部分性能瓶颈都出在"数据组织不当"或"算法选择不当"上。会写循环只能解决"能不能跑"，懂复杂度才能回答"够不够快"。

如何学好数据结构和算法

很多同学学这门课时的状态是：上课听懂了，看书看懂了，一动手写代码就懵。这里分享两条被无数人验证过的秘诀。

秘诀一：死磕代码！

光看不算会，光听不算会，只有自己一行行敲出来、调通、跑出正确结果，才算真的掌握。建议每学完一个结构（比如链表），就亲手实现一遍：增、删、查、改全写一遍。写不出来就对着书抄，抄完合上书再写一遍，直到能独立默写出来。这个过程很痛苦，但绝对是提升最快的方式。

秘诀二：画图画图画图 + 思考！

数据结构是"结构"，天然适合用图来表达。链表的插入、二叉树的旋转、指针的交换指向……光在脑子里想很容易绕晕，拿张纸画出来，或者用调试器逐步观察内存，一切豁然开朗。先画图，再写代码，是一个能让你少掉一半头发的好习惯。

值得反复翻阅的经典书籍

算法效率：先从旋转数组说起

铺垫了这么多，现在进入正题：如何衡量一个算法的好坏？

先看一个真实的题目。LeetCode 189 题——旋转数组：给定一个数组，将数组中的元素向右轮转 k 个位置。例如 nums = [1,2,3,4,5,6,7]，k = 3，轮转后变成 [5,6,7,1,2,3,4]。

拿到题，很多人的第一反应是：循环 K 次，每次把整个数组所有元素向后移动一位。代码很快就写出来了：

#include <stdio.h>
 
// 旋转数组：循环 k 次，每次把所有元素整体后移一位
void rotate(int* nums, int numsSize, int k)
{
    while (k--)  // 轮转 k 次
    {
        // 1. 先保存最后一个元素，因为它会被覆盖
        int end = nums[numsSize - 1];
 
        // 2. 从后往前，把每个元素挪到后一个位置上
        for (int i = numsSize - 1; i > 0; i--)
        {
            nums[i] = nums[i - 1];
        }
 
        // 3. 把保存的最后一个元素放到第一个位置
        nums[0] = end;
    }
}
 
int main()
{
    int nums[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(nums) / sizeof(nums[0]);
    int k = 3;
 
    rotate(nums, n, k);
 
    for (int i = 0; i < n; i++)
        printf("%d ", nums[i]);   // 输出：5 6 7 1 2 3 4
    printf("\n");
    return 0;
}

这个代码对不对？逻辑上完全正确，结果也分毫不差。但诡异的事情来了：你在 LeetCode 上点击"执行"（Run），可以通过；点击"提交"（Submit），却无法通过——会得到"超出时间限制"（Time Limit Exceeded）的判罚。

这是为什么？代码没错，为什么不让过？

答案就是：这道题的数据规模很大，你的算法太慢了。 LeetCode 的评测数据里 numsSize 可能高达几十万，k 也可能很大，循环 K 次 × 每次移动 N 个元素，总操作量是 N × K 这个量级，几千万上亿次操作，超时在所难免。

这就引出了本课程最重要的一个概念——复杂度。我们需要一种方法，在不运行程序的情况下，就能从理论上估算出一个算法的优劣。这正是复杂度存在的意义。

复杂度的概念

算法在编写成可执行程序后，运行时需要耗费两类资源：时间资源和空间（内存）资源。因此衡量一个算法的好坏，一般从两个维度出发：

• 时间复杂度：主要衡量一个算法的运行快慢；
• 空间复杂度：主要衡量一个算法运行所需要的额外空间。

这里有个有意思的历史背景：在计算机发展的早期，存储容量非常小（内存按 KB 计算），程序稍不注意就会把内存撑爆，所以那时的人们对空间复杂度非常在乎。而经过几十年的飞速发展，计算机的存储容量已经达到很高的程度，如今我们不再需要特别关注一个算法的空间复杂度——只要不是指数级地申请空间，一般都能接受。现在的首要矛盾，是算法跑得快不快。

时间复杂度

为什么不能直接测运行时间

先看定义：在计算机科学中，算法的时间复杂度是一个函数式 T(N)，它定量描述了该算法的运行时间。

等等，既然要描述运行时间，为什么不直接把程序跑一遍、掐个秒表，多简单？这里有三个无法回避的理由：

1. 编译环境不同：同一个算法程序，用老编译器编译和新编译器编译，在同样机器下运行时间不同——编译优化、指令生成都有差异；
2. 运行机器配置不同：同一个算法程序，在低配置机器和高配置机器上运行时间也不同——CPU 主频、内存带宽都不一样；
3. 时间只能"事后"测：程序必须写完才能跑、才能测，没法在写程序之前通过理论思想计算评估——而我们恰恰需要在动笔之前就判断思路靠不靠谱。

结论：直接测运行时间这条路走不通，我们需要一个脱离具体软硬件环境的、纯理论的衡量标准。

T(N)：算的是执行次数，不是时间

那 T(N) 到底是什么？答案是：T(N) 函数式计算的是程序的执行次数。

回顾编译链接的知识：算法程序被编译后生成二进制指令，程序运行的过程，就是 CPU 逐条执行这些指令的过程。而同一段代码，无论在哪台机器上编译运行，它的**指令条数（执行次数）**是基本确定的。假设每条指令执行时间基本一样（实际有细微差别，但微乎其微），那么：

执行次数 和 运行时间 是等比正相关的。

既然执行次数能代表运行时间，又和具体环境无关，那我们干脆用"执行次数"作为衡量算法时间效率的标尺。比如解决同一个问题：

• 算法 A 的 T(N) = N
• 算法 B 的 T(N) = N²

那么可以断定：算法 A 的效率一定优于算法 B——不管跑在哪台机器上。

来看一个具体的例子，计算下面这段代码中 ++count 语句总共执行了多少次：

// 请计算 Func1 中 ++count 语句总共执行了多少次？
void Func1(int N)
{
    int count = 0;
 
    // 双重循环：i 每取一个值，j 都要从 0 跑到 N-1，共执行 N*N 次
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            ++count;
        }
    }
 
    // 单层循环：执行 2*N 次
    for (int k = 0; k < 2 * N; ++k)
    {
        ++count;
    }
 
    int M = 10;
    while (M--)  // 循环 10 次
    {
        ++count;
    }
}

逐段统计：嵌套循环执行 N * N 次，单层循环执行 2 * N 次，while 循环执行 10 次。加起来：

T(N) = N² + 2N + 10

分别代入不同的 N 看看结果：

看出来了吗？当 N 不断变大，对结果影响最大的永远是 N² 那一项。2N 和 10 这些低阶项、常数项，占比越来越小，小到可以忽略不计。

这也揭示了复杂度的核心思想：我们关心的是"当 N 不断变大时，T(N) 的增长量级"，而不是精确的执行次数。毕竟，不同语句编译出的指令条数各不相同，算精确执行次数既麻烦又没有意义——我们只是想比较不同算法程序的增长量级。复杂度的表示，通常使用大 O 的渐进表示法。

大O的渐进表示法

大 O 符号（Big O notation）是用于描述函数渐进行为的数学符号。它不关心"到底执行多少次"，只关心"当输入规模 N 趋于无穷大时，执行次数按什么速度增长"。

从 T(N) = N² + 2N + 10 推出 O(N²)，依据的是下面三条推导规则——这三条规则是整个复杂度计算的核心，请务必刻进脑子里：

规则 1：只保留最高阶项，去掉低阶项。 当 N 不断变大时，低阶项对结果影响越来越小；当 N 无穷大时，低阶项就可以忽略不计了。N² + 2N + 10 中，最高阶是 N²，2N 和 10 全部划掉。

规则 2：如果最高阶项存在且不是 1，去掉它的常数系数。 当 N 无穷大时，系数对增长量级没有影响。2N² 和 N² 的增长速度完全一致，都是"平方级"，所以系数直接删掉。比如 T(N) = 3N² + 5N → O(N²)。

规则 3：如果 T(N) 中没有和 N 相关的项、只有常数项，用常数 1 取代所有加法常数。 比如 T(N) = 100，执行次数恒为 100，不随 N 变化，记作 O(1)（读作"常数阶"）。

回到 Func1：T(N) = N² + 2N + 10，按规则 1 去掉低阶项 2N + 10，得到：

Func1 的时间复杂度为 O(N²)

记住这个思路：先写出精确的 T(N)，再按三条规则化简成 O(...)。接下来我们用 7 个经典示例，把这个流程练到滚瓜烂熟。

时间复杂度计算示例

示例 1：Func2 —— O(N)

// 计算 Func2 的时间复杂度？
void Func2(int N)
{
    int count = 0;
 
    for (int k = 0; k < 2 * N; ++k)  // 循环 2*N 次
    {
        ++count;
    }
 
    int M = 10;
    while (M--)  // 循环 10 次
    {
        ++count;
    }
 
    printf("%d\n", count);
}

精确执行次数：T(N) = 2N + 10。

按规则化简：最高阶项是 2N，低阶项 10 去掉（规则 1）；最高阶项系数 2 去掉（规则 2）。得到：

Func2 的时间复杂度为 O(N)

示例 2：Func3 —— O(M+N)

// 计算 Func3 的时间复杂度？
void Func3(int N, int M)
{
    int count = 0;
 
    for (int k = 0; k < M; ++k)  // 循环 M 次
    {
        ++count;
    }
 
    for (int k = 0; k < N; ++k)  // 循环 N 次
    {
        ++count;
    }
 
    printf("%d\n", count);
}

精确执行次数：T(N) = M + N。

这里有个新手常踩的坑：M 和 N 是两个独立的未知数，我们不知道谁大谁小，无法确定谁是"最高阶项"，所以两个都要保留：

Func3 的时间复杂度为 O(M + N)

示例 3：Func4 —— O(1)

// 计算 Func4 的时间复杂度？
void Func4(int N)
{
    int count = 0;
 
    for (int k = 0; k < 100; ++k)  // 无论 N 是多少，都固定循环 100 次
    {
        ++count;
    }
 
    printf("%d\n", count);
}

精确执行次数：T(N) = 100。这里注意：循环次数与 N 毫无关系，N 取 1 还是取 10 亿，都是 100 次。

按规则 3，没有 N 相关项、只有常数项，用 1 取代：

Func4 的时间复杂度为 O(1)

示例 4：strchr —— 最好/最坏/平均

strchr 是标准库函数，在字符串中查找某个字符第一次出现的位置。看它的典型实现：

#include <stdio.h>
 
// 在字符串 str 中查找字符 character，找到返回指向它的指针，找不到返回 NULL
const char* strchr(const char* str, int character)
{
    const char* p_begin = str;  // 从字符串开头开始查找
 
    while (*p_begin != character)
    {
        if (*p_begin == '\0')   // 已经走到字符串结尾还没找到
            return NULL;        // 返回空指针
 
        p_begin++;              // 继续向后查找
    }
 
    return p_begin;             // 找到了，返回指向该字符的指针
}

它的执行次数取决于目标字符在字符串中的位置：

因此 strchr 的时间复杂度有三种说法：

• 最好情况：O(1) —— 任意输入规模的最小运行次数（下界）；
• 最坏情况：O(N) —— 任意输入规模的最大运行次数（上界）；
• 平均情况：O(N) —— 任意输入规模的期望运行次数。

示例 5：BubbleSort —— 最好 O(N) / 最坏 O(N²)

#include <assert.h>
 
// 交换两个整数
void Swap(int* pa, int* pb)
{
    int tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}
 
// 冒泡排序：对数组 a 的前 n 个元素升序排序
void BubbleSort(int* a, int n)
{
    assert(a);  // 断言传入的指针有效
 
    // 外层循环：每趟确定一个最大值放到末尾
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;  // 标记本趟是否发生过交换
 
        // 内层循环：相邻元素两两比较
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;  // 发生过交换，打上标记
            }
        }
 
        // 如果本趟没有发生任何交换，说明数组已经有序，提前结束
        if (exchange == 0)
            break;
    }
}

冒泡排序的执行次数和数据的初始有序程度密切相关：

情况 1：数组本身有序。 第一趟扫描，从头到尾比较了 N - 1 次，一次交换都没发生，exchange == 0，直接 break 退出。所以 T(N) = N - 1，复杂度 O(N)——这是最好情况。

情况 2：数组完全逆序（降序）。 这是最坏情况：每一趟都要完整比较，第 1 趟比较 N-1 次，第 2 趟 N-2 次，……最后一趟 1 次。总次数是一个等差数列求和：

T(N) = (N-1) + (N-2) + ... + 1 = N*(N-1)/2 ≈ N²/2

按规则去掉系数和低阶项：O(N²)。

所以 BubbleSort 的时间复杂度取最坏情况，记作 O(N²)。这里也印证了前面"大O看最坏上界"的原则——最坏情况 O(N²) 才是这个算法性能的真实下限保障。

示例 6：func5 —— O(log₂N)

// 计算 func5 的时间复杂度？
void func5(int n)
{
    int cnt = 1;
 
    while (cnt < n)
    {
        cnt *= 2;  // 每次翻倍
    }
}

这个循环的执行次数就不是"数循环层数"能看出来的了，得分析 cnt 的增长规律：

初始  cnt = 1
第 1 次后  cnt = 2
第 2 次后  cnt = 4
第 3 次后  cnt = 8
...
第 x 次后  cnt = 2^x

循环终止条件是 cnt >= n，也就是要满足 2^x >= n。代入几个具体值验证：当 n=2 时，执行 1 次；n=4 时，执行 2 次；n=16 时，执行 4 次。可见执行次数 x 和 n 的关系是：

2^x = n ⟹ x = log₂n

因此 func5 的时间复杂度为 O(log₂n)，一般写作 O(log n)（对数阶）。

对数阶是非常优秀的复杂度——想想看，n = 100 万时，log₂n ≈ 20，循环只需要跑约 20 次！二分查找就是对数阶的经典代表。

示例 7：阶乘递归 Fac —— O(N)

递归的时间复杂度计算是个新玩法，思路要转换：递归的时间复杂度 = 每次递归调用的时间复杂度 × 递归调用的次数。

// 计算阶乘递归 Fac 的时间复杂度？
long long Fac(size_t N)
{
    if (0 == N)      // 终止条件：0! = 1
        return 1;
 
    return Fac(N - 1) * N;  // N! = N * (N-1)!，继续递归
}

分两步分析：

1. 调用一次 Fac 函数：里面只有一次 if 判断和一次乘法，时间复杂度为 O(1)；
2. 递归调用了多少次：Fac(N) 会调用 Fac(N-1)，后者再调用 Fac(N-2)……一路递归到 Fac(0) 才停止，一共调用了 N 次。

总的时间复杂度 = O(1) × N = O(N)。

Fac(N)
  → Fac(N-1)     第 1 次调用，O(1)
      → Fac(N-2) 第 2 次调用，O(1)
          → ...
              → Fac(0)  第 N 次调用，O(1)

示例 8：斐波那契朴素递归 —— O(2ⁿ)，递归的"深水区"

阶乘递归是一条线，递归函数只调用一次自己。但很多递归会分叉——一次调用自己两次甚至更多次，斐波那契数列的朴素递归就是最典型的例子：

// 计算斐波那契数列第 N 项（朴素递归版）
// 斐波那契数列：1, 1, 2, 3, 5, 8, 13, ...，前两项是 1，从第 3 项起每项 = 前两项之和
long long Fib(size_t N)
{
    if (N < 3)                        // 第 1、2 项都是 1
        return 1;
 
    return Fib(N - 1) + Fib(N - 2);   // 第 N 项 = 前两项之和，递归展开时会分叉！
}

注意看，Fib(N) 要调 Fib(N-1) 和 Fib(N-2) 两个函数，这两个又各自往下分叉。递归调用不再是"一条直线"而是"一棵不断分叉的树"，前面"单次复杂度 × 调用深度"的速记公式失效了——因为调用次数本身就不是线性的。我们得换一种工具：把递归的展开过程画成一棵树，用展开法（也叫递归树法）来推。

以 Fib(5) 为例，它的完整调用过程长这样：

Fib(5)
├── Fib(4)
│   ├── Fib(3)
│   │   ├── Fib(2)
│   │   └── Fib(1)
│   └── Fib(2)
└── Fib(3)
    ├── Fib(2)
    └── Fib(1)

数一数：Fib(5) 一共触发了 9 次函数调用（不含它自己）。直观上，树有多少结点，就做了多少"单次 O(1)"的工作。而这是一棵"结点数按层指数增长"的树——第 1 层 1 个、第 2 层 2 个、第 3 层 4 个……最深层大约有 2^(N/2) 个叶子。整棵树的结点数，量级就是 O(2ⁿ)。

更严谨的推导用展开法。设 Fib(N) 的时间函数为 T(N)，一次调用本身是 O(1)（一次 if 判断、一次加法），递归体是：

T(N) = T(N-1) + T(N-2) + O(1)         ①

这个递推式不是主定理的标准形式（后面会讲主定理），我们就暴力展开。先做一个放缩：T(N-1) > T(N-2)，所以：

T(N) = T(N-1) + T(N-2) + 1
     > 2·T(N-2)                       ②  （把 T(N-1) 放缩成 T(N-2)，两项并一项）

对 ② 继续展开，每展开一层，规模 N 减 2、系数乘 2：

T(N) > 2·T(N-2)
     > 2²·T(N-4)
     > 2³·T(N-6)
     > ...
     > 2^k·T(N-2k)

展开到 N - 2k = 2（基准情形）时，k ≈ N/2，此时 T(N) > 2^(N/2)·O(1)，也就是 T(N) = Ω(2^(N/2))——下限已经是指数级。再结合每层都分叉、不存在中途合并不返回的浪费，可以推出上界同样是 2^N 量级，所以：

到这里，8 个时间复杂度示例全部攻破。我们来梳理一下计算时间复杂度的通用套路：

1. 找核心操作：找出循环体/递归体里重复执行的那条语句；
2. 数执行次数：推导出关于 N 的精确表达式 T(N)；
3. 按三条规则化简：去低阶、去系数、常数变 1，得出 O(...)。

递归复杂度的深水区：展开法与主定理

递归的复杂度是复杂度分析的进阶内容，面试和竞赛里频繁出现。除了"画递归树"这种直观方法，还有两把更趁手的工具：展开法和主定理。它们解决的是同一类问题——给你一个递推式（比如 T(N) = 2T(N/2) + N），让你判断它最终的量级。

展开法：把递推式一层层剥开

展开法的思路非常朴素：把递推式反复代入，直到露出基准情形，然后观察规律。刚才的斐波那契就是这么推的。再看一个规整的例子——归并排序的时间函数。它把一个规模 N 的问题拆成两个规模 N/2 的子问题，每个子问题内部继续递归，合并两个有序数组的代价是 O(N)（扫描一遍），于是有：

T(N) = 2T(N/2) + N       ①    （N > 1）
T(1) = 1                        （基准情形）

逐层展开：

T(N)   = 2T(N/2)   + N
       = 2[2T(N/4) + N/2] + N         ← 把 T(N/2) = 2T(N/4) + N/2 代进来
       = 4T(N/4)   + 2N
       = 4[2T(N/8) + N/4] + 2N        ← 再把 T(N/4) 代进来
       = 8T(N/8)   + 3N
       = ...
       = 2^k·T(N/2^k) + k·N           ← 展开 k 层后的规律

展开 k 层后，第一项系数是 2^k，第二项是 k·N。什么时候停？当 N/2^k = 1，即 2^k = N，也就是 k = log₂N 时到达基准情形。代入：

T(N) = 2^(log₂N)·T(1) + log₂N·N
     = N·1 + N·log₂N
     = O(N·logN)

看，每一层递归的"合并代价"是 N（被摊到该层的所有子问题上），一共有 log₂N 层，总代价就是 N·logN。这和我们后面讲归并排序时"树高 logN、每层 O(N)"的说法完全一致——展开法把同一件事换了个数学视角。

主定理：一张表秒杀常见递推式

展开法每次都要手动推，稍烦。对于形如 T(N) = a·T(N/b) + f(N) 的递推式（a 个子问题、每个规模变为 N/b、额外代价 f(N)），可以直接套用主定理（Master Theorem）。核心是拿 f(N) 和 N^(log_b a) 比大小：

注意"高于/低于"说的是多项式意义上的阶（差一个 N^ε，ε > 0），不是差一个常数或 log 因子，所以主定理有少量覆盖不到的灰色地带（比如 f(N) = N·logN 与 N^1 比较的情形 2 边缘），考试和面试遇到的那几个经典递推式基本都能覆盖。

用主定理快速验证几个最常见的递推式：

逐个品一品：二分查找每次砍半、单次代价 O(1)，自然是 logN；二叉树遍历（前中后序）每个结点恰好访问一次，虽然递归树有 N 个结点，但总代价 Θ(N)——主定理的情形 1 说的正是"叶子太多时，每层那点额外工作可以忽略"。快速排序的平均情况（划分大致对半）就是 T(N) = 2T(N/2) + N，所以是 Θ(N·logN)；而最坏情况（每次划分都极度不平衡）递推式变成 T(N) = T(N-1) + N，展开得 N + (N-1) + ... + 1 = N(N+1)/2 = Θ(N²)，这正是快排最坏 O(N²) 的数学来源，后面排序章节会详细讲。

到这里，递归复杂度的两把工具就齐了：遇到分叉递归先画递归树找直觉，遇到规整递推式用展开法或主定理收口。加上前面 8 个示例，时间复杂度的计算你已经覆盖了循环、顺序执行、二分、递归全部常见形态。

空间复杂度

讲完时间维度，再来看空间维度。空间复杂度也是一个数学表达式，它描述一个算法在运行过程中，因为算法的需要额外临时开辟的空间大小。

两个关键点，先纠正两个常见误区：

误区一：空间复杂度算的是字节数吗？ 不是。空间复杂度不是程序占用了多少 bytes 的空间，因为常规情况下每个对象的大小差异不会很大，所以空间复杂度算的是变量的个数。申请了 3 个变量就是常数个，申请了 N 个变量的数组就是 O(N)。

误区二：函数栈帧算不算额外空间？ 这里有个精妙的规则：函数运行时所需要的栈空间（存储参数、局部变量、寄存器信息等）在编译期间就已经确定好了。也就是说，调用一个函数要占多少栈空间，编译器早就定死了，不需要运行时"额外"申请。因此：

空间复杂度主要看函数在运行过程中显式申请的额外空间。

比如函数里定义了一个 int exchange，这是编译期确定的局部变量，属于"常规开销"，不算额外空间；但如果在函数里 malloc 了一个长度为 N 的数组，这就是显式申请的额外空间，算 O(N)。

空间复杂度的计算规则基本与时间复杂度类似，同样使用大 O 渐进表示法。

空间复杂度计算示例

示例 1：BubbleSort —— O(1)

#include <assert.h>
 
// 交换两个整数
void Swap(int* pa, int* pb)
{
    int tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}
 
// 冒泡排序：对数组 a 的前 n 个元素升序排序
void BubbleSort(int* a, int n)
{
    assert(a);  // 断言传入的指针有效
 
    // 外层循环：每趟确定一个最大值放到末尾
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;  // 标记本趟是否发生过交换
 
        // 内层循环：相邻元素两两比较
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
 
        if (exchange == 0)  // 数组已有序，提前结束
            break;
    }
}

分析 BubbleSort 的空间占用：

• 参数 a、n、循环变量 end、i、局部变量 exchange，这些都是编译期确定的栈空间，属于函数运行的基本开销；
• 函数体内没有显式申请任何额外空间——没有 malloc，没有动态数组，Swap 里那个 tmp 也只是常数个局部变量。

所以 BubbleSort 只使用了常数个额外空间：

BubbleSort 的空间复杂度为 O(1)

注意，这里必须想明白一件事：排序操作是在传入的数组 a 上原地完成的，这个数组是调用者提供的，不属于算法"额外"开辟的空间。

示例 2：阶乘递归 Fac —— O(N)

// 计算阶乘递归 Fac 的空间复杂度？
long long Fac(size_t N)
{
    if (N == 0)  // 终止条件
        return 1;
 
    return Fac(N - 1) * N;  // 继续递归
}

这个例子的结论和 BubbleSort 完全相反。关键在于递归调用会层层累积栈帧：

回顾递归知识：每次函数调用，都会在栈区开辟一块栈帧空间（保存局部变量和返回地址），函数返回后这块空间才会释放。Fac(N) 调用 Fac(N-1)，栈帧先不释放；Fac(N-1) 又调用 Fac(N-2)，栈帧继续累积……直到 Fac(0) 返回，才开始一层层释放。

栈区空间增长方向（示意）：
┌──────────────┐  ← 栈顶
│ Fac(0) 的栈帧 │    第 N 层，返回后释放
├──────────────┤
│ Fac(1) 的栈帧 │    第 N-1 层
├──────────────┤
│   ...        │
├──────────────┤
│ Fac(N-1) 的栈帧│    第 2 层
├──────────────┤
│ Fac(N) 的栈帧 │    第 1 层
└──────────────┘

所以：

• Fac 递归调用了 N 次，也就是额外开辟了 N 个函数栈帧；
• 每个栈帧只使用常数个空间（保存参数 N、返回地址等）。

N 个栈帧 × 常数空间 = ：

Fac 递归的空间复杂度为 O(N)

常见复杂度对比

学完了计算方法，我们来横向对比一下常见复杂度的增长量级。下面这张表，代入 N = 10 / 100 / 1000，看看各个复杂度分别需要执行多少次：

从表格可以直观地感受到几个事实：

1. O(1) 和 O(log n) 是"永远的神"：N 从 10 涨到 1000，它们的执行次数几乎纹丝不动；
2. O(N²) 及以上的复杂度很危险：N 到 1000 时，O(N²) 已经要执行 100 万次，O(N³) 更是到了 10 亿次，O(2ⁿ) 和 O(N!) 直接不可想象；
3. 工程实践中 O(N·log n) 是"黄金复杂度"：快排、归并排序等主流排序算法都落在这个量级，兼顾了速度和可实现性。

一个更直观的对比，当 N 持续增大时各复杂度的增长速度曲线：

执行次数
  │
  │                        O(N!)
  │                      O(2ⁿ)
  │                  O(N³)
  │               O(N²)
  │          O(N·log n)
  │      O(N)
  │  O(log n)
  │O(1)
  └───────────────────────────→ N

复杂度分析的高频误区

复杂度看似简单，但初学者（甚至不少工作多年的程序员）在五个地方反复栽跟头。把它们单独拎出来说透，能帮你少走很多弯路。

误区一：把 O(1) 理解成"只执行 1 次"。 前面已经强调过，O(1) 的意思是"执行次数不随输入规模 N 变化"，是一个固定的常数——哪怕这个常数是 10 万。同理，O(2)、O(100) 这种写法在数学上存在，但在复杂度分析里都写作 O(1)，因为常数没有量级之分。所以判断标准永远只有一个：这个操作的次数跟 N 有关系吗？没有，就是 O(1)。

误区二：只记"平均情况"，忘了看最坏情况。 大 O 关注的是最坏上界——它给你性能保证。比如哈希表平均查找 O(1)，但极端的哈希冲突下会退化到 O(N)；快排平均 O(N·logN)，但有序数组 + 固定取最左为基准会退化到 O(N²)。面试官问"这个算法复杂度是多少"，默认是在问最坏情况，除非题目明确说"平均"。写代码时也是同样的态度：如果最坏情况会发生且代价巨大（比如在 O(N²) 的路径上跑 100 万条数据），就必须想办法规避。

误区三：纠结 log 的底数，或者纠结"是 log 还是 log²"。 log 的底数已被证明可以忽略（换底公式差常数倍）。而"到底差一个 log 因子还是两个"，比如 O(N·logN) 和 O(N·log²N)，这个差别是真实存在的（N=10⁶ 时约差 20 倍），不能混为一谈——分析时该精确的地方要精确，该忽略常数的地方才忽略。

误区四：把"均摊"当成"每一次都很快"。 动态数组扩容、双栈实现队列，都是"偶尔一次很贵，但整体均摊下来很快"的例子。均摊 O(1) 说的是连续做 m 次操作的总代价是 O(m)，不代表其中某一次不慢——插入恰好触发扩容那一次，就是实打实的 O(N)。理解这个区别，才能解释"为什么 ArrayList 扩容是 2 倍而不是每次 +1"。

误区五：用"运行时间"代替"渐近复杂度"。 有人拿 clock() 实测两个算法，发现 O(N²) 的比 O(NlogN) 的还快，就怀疑复杂度分析是错的。真相是：复杂度描述的是 N 足够大时的增长趋势，N 很小（比如 N = 10）时，常数因子、缓存、编译器优化都能让结论反转。所以正确姿势是：小数据看常数，大数据看渐近——渐近复杂度决定"天花板"，常数因子决定"同一档位里的快慢"。

复杂度算法题：旋转数组的三种解法

现在，带着完整的大 O 武器库，回到开头那道让我们铩羽而归的旋转数组。题目回顾：nums = [1,2,3,4,5,6,7]，k = 3，要求输出 [5,6,7,1,2,3,4]。

我们来逐一分析三种思路的复杂度，看看谁才是最优解。

思路 1：循环 K 次整体移动 —— O(N²)，超时

就是开头那段代码：循环 K 次，每次把数组所有元素后移一位。

分析复杂度：外层循环 K 次，内层循环移动 N 个元素，所以：

T(N) = N × K，最坏情况（K 与 N 同量级）下是 O(N²)

这就是它"能过执行、不能过提交"的根本原因——当 N 和 K 达到题目的大数据规模时，O(N²) 的上亿次操作直接超时。

执行过程（N=7, K=1）：
原始数组   1 2 3 4 5 6 7
第 1 次循环：7 1 2 3 4 5 6    ← 所有元素后移一位，7 绕到最前面
（重复 K 次）

结论：思路可行，但效率不合格，需要优化。

思路 2：申请新数组 —— O(N) 时间，O(N) 空间

思路 1 慢在"反复移动"。能不能一步到位？可以——申请一个新数组，直接把每个元素放到它最终该去的位置上：原来下标 i 的元素，轮转后应该去下标 (i + k) % N 的位置。

#include <stdio.h>
 
// 旋转数组：申请新数组，一步定位每个元素的最终位置
void rotate(int* nums, int numsSize, int k)
{
    // 申请一个和原数组等大的新数组（变长数组，C99 支持）
    int newArr[numsSize];
 
    // 第一步：把每个元素一次性放到它的最终位置
    // 原来下标 i 的元素，轮转 k 位后到达 (i + k) % numsSize
    for (int i = 0; i < numsSize; ++i)
    {
        newArr[(i + k) % numsSize] = nums[i];
    }
 
    // 第二步：把新数组的内容拷回原数组
    for (int i = 0; i < numsSize; ++i)
    {
        nums[i] = newArr[i];
    }
}
 
int main()
{
    int nums[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(nums) / sizeof(nums[0]);
    int k = 3;
 
    rotate(nums, n, k);
 
    for (int i = 0; i < n; i++)
        printf("%d ", nums[i]);   // 输出：5 6 7 1 2 3 4
    printf("\n");
    return 0;
}

复杂度分析：

• 时间复杂度：两个循环，每个循环 N 次，总共 2N 次操作，O(N)；
• 空间复杂度：显式申请了一个长度 N 的新数组，O(N)。

定位过程（N=7, K=3）：
原数组下标   0  1  2  3  4  5  6
原数组元素   1  2  3  4  5  6  7
              ↓  ↓  ↓  ↓  ↓  ↓  ↓
目标下标 (i+3)%7: 3  4  5  6  0  1  2
新数组       4  5  6  7  1  2  3
再拷回原数组 → 4 5 6 7 1 2 3

时间上已经达标（O(N)），但空间上还有优化空间——能不能不申请新数组，原地完成？ 这就轮到思路 3 了。

思路 3：三段逆置 —— O(N) 时间，O(1) 空间

先看一个神奇的规律。以 [1,2,3,4,5,6,7]、k = 3 为例（此时 n - k = 4，k = 3）：

原始数组：  1 2 3 4 | 5 6 7
              ↑前 n-k 个↑   ↑后 k 个↑

第 1 步：逆置前 n-k 个    → 4 3 2 1 | 5 6 7
第 2 步：逆置后 k 个      → 4 3 2 1 | 7 6 5
第 3 步：整体逆置         → 5 6 7 1 2 3 4   ✓ 目标达成！

三步逆置之后，数组恰好轮转了 k 位。这个技巧的妙处在于：只用常数个额外变量（tmp），完全原地完成。先实现一个逆置辅助函数：

// 逆置数组中 [begin, end] 闭区间内的元素
void reverse(int* nums, int begin, int end)
{
    while (begin < end)
    {
        // 交换首尾两个元素
        int tmp = nums[begin];
        nums[begin] = nums[end];
        nums[end] = tmp;
 
        begin++;  // 左指针向右移动
        end--;    // 右指针向左移动
    }
}

然后主函数只需要三行：

#include <stdio.h>
 
// 旋转数组：三段逆置法，原地完成，空间 O(1)
void rotate(int* nums, int numsSize, int k)
{
    k = k % numsSize;  // 关键：k 可能大于数组长度，取模处理（轮转 N 次等于没转）
 
    reverse(nums, 0, numsSize - k - 1);        // 第 1 步：逆置前 n-k 个
    reverse(nums, numsSize - k, numsSize - 1); // 第 2 步：逆置后 k 个
    reverse(nums, 0, numsSize - 1);            // 第 3 步：整体逆置
}
 
int main()
{
    int nums[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(nums) / sizeof(nums[0]);
    int k = 3;
 
    rotate(nums, n, k);
 
    for (int i = 0; i < n; i++)
        printf("%d ", nums[i]);   // 输出：5 6 7 1 2 3 4
    printf("\n");
    return 0;
}

三步逆置的完整推演（N=7，K=3，k % n = 3）：

原始数组：  1   2   3   4   5   6   7
            └──────┬──────┘   └──┬──┘
               前 n-k=4 个       后 k=3 个

第 1 步：逆置前 4 个
           1   2   3   4   →   4   3   2   1
   结果：  4   3   2   1   5   6   7

第 2 步：逆置后 3 个
           5   6   7   →   7   6   5
   结果：  4   3   2   1   7   6   5

第 3 步：整体逆置
           4   3   2   1   7   6   5   →  5   6   7   1   2   3   4   ✓

复杂度分析：

• 时间复杂度：三次 reverse，每次逆置遍历一部分元素，每个元素恰好被逆置两次，总共约 2N 次操作，O(N)；
• 空间复杂度：只有一个 tmp 变量和两个下标指针，O(1)。

三种解法对比总结

从超时的 O(N²) 到通过的 O(N)，从 O(N) 的额外空间压到 O(1)——这一个题目，把时间复杂度、空间复杂度、以及"空间换时间"的权衡全部串了起来。这就是复杂度的威力：在动手写代码之前，就能判断一个思路能不能过，而不是等提交之后才发现超时。

回到文章开头的书架。同样是找一本书，随性堆放和分类摆放，效率天差地别；同样是解决一个问题，暴力思路和巧妙思路，性能可能差出几个数量级。而复杂度分析，就是你衡量这一切的标尺。从今天起，写完一段代码，先问自己一句：它的时间复杂度是多少？空间复杂度呢？有没有更优的解法？养成这个习惯，你就已经迈出了从"会写代码"到"写好代码"的第一步。

思考题与练习

学完不等于会了，动手才算数。下面这些题覆盖了本章的全部核心知识点，先自己算，再对照提示验证。

练习 1：写出下列代码的时间复杂度（N 为数据规模）。

// 练习 1.1
void funcA(int N)
{
    int count = 0;                        // 计数变量，统计核心操作执行次数
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < i; ++j)   // 注意内层循环次数随 i 变化
            ++count;
}

// 练习 1.2
void funcB(int N)
{
    int count = 0;
    for (int i = 1; i <= N; i *= 2)   // 循环变量翻倍
        ++count;
}

// 练习 1.3
void funcC(int N)
{
    int count = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 1; j < N; j *= 2)
            ++count;
}

练习 2：递归复杂度。 求下列递归函数的时间复杂度和空间复杂度，并用展开法写出推导过程。

// 练习 2.1
int pow2(int n)                // 计算 2 的 n 次方
{
    if (n == 0) return 1;
    return 2 * pow2(n - 1);
}
 
// 练习 2.2
int fastPow2(int n)            // 快速幂的朴素版本
{
    if (n == 0) return 1;
    int half = fastPow2(n / 2);
    return half * half;
}

练习 3：三段逆置的变体。 题目改成"将数组向左轮转 k 个位置"（比如 [1,2,3,4,5,6,7] 左转 3 位变成 [4,5,6,7,1,2,3]），三段逆置怎么改？

练习 4：空间复杂度判断。 下面的函数空间复杂度是多少？有人说"它 malloc 了 N 个空间，所以是 O(N)"，对吗？

#include <string.h>   // memset
#include <stdlib.h>   // malloc / free
 
void funcD(int N)
{
    int* p = (int*)malloc(sizeof(int) * N);
    if (p == NULL) return;
    memset(p, 0, sizeof(int) * N);
    free(p);
}

练习 5（挑战）： 朴素递归求斐波那契的时间复杂度是 O(2ⁿ)。给它加一个"记忆化"数组（把算过的 Fib(i) 存下来，下次直接用），时间复杂度变成多少？

下一课，我们将用这张"复杂度标尺"，去丈量第一个真正的数据结构——顺序表和链表。