如何分析一段代码的复杂度

学习目标

本节把前面的概念落到具体代码分析上。

学习目标是掌握一个基本流程：先确定输入规模，再找关键操作，然后分析循环、嵌套循环、递归或额外空间，最后用大 O 表示法简化结果。

分析复杂度的基本步骤

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

明确输入规模是什么，例如数组长度 $n$ 、字符串长度 $n$ ，或者图中的顶点数 $V$ 和边数 $E$ 。
找出关键操作，例如比较、访问、插入、删除或输出。
分析关键操作会执行多少次。
如果有多段代码顺序执行，把成本相加，再保留增长最快的部分。
如果有嵌套循环，通常要观察每层循环次数之间的关系。
如果有递归，要分析递归调用次数、递归深度和每层额外工作量。
最后用大 O 表示法忽略常数和低阶项。

这套步骤不是机械公式，而是帮助你避免遗漏关键信息。

顺序语句通常是常数级

如果代码只执行固定数量的语句，而且这些语句不随输入规模增长，那么时间复杂度通常是 $O(1)$ 。

读取一个变量
修改一个变量
返回一个结果

无论输入集合有多大，只要这几步本身没有遍历集合，就可以看作常数级操作。

单层循环通常是线性级

下面的代码会统计正数个数。它必须检查每个元素一次，所以时间复杂度是 $O(n)$ 。

int countPositive(const vector<int>& numbers) {
    int count = 0;

    for (int number : numbers) {
        if (number > 0) {
            count++;
        }
    }

    return count;
}

int countPositive(int[] numbers) {
    int count = 0;

    for (int number : numbers) {
        if (number > 0) {
            count++;
        }
    }

    return count;
}

def count_positive(numbers):
    count = 0

    for number in numbers:
        if number > 0:
            count += 1

    return count

int CountPositive(int[] numbers)
{
    int count = 0;

    foreach (int number in numbers)
    {
        if (number > 0)
        {
            count++;
        }
    }

    return count;
}

这里的关键操作是判断 number > 0。数组中有 $n$ 个元素，判断就会执行 $n$ 次。

独立循环相加后保留主导项

如果一段代码先遍历一次数组，再进行两层嵌套循环，可以先把它们的成本相加。

第一段：n 次
第二段：n × n 次
总成本：n + n²

根据大 O 简化规则，最终保留增长更快的 $n^2$ ，所以复杂度是 $O(n^2)$ 。

嵌套循环不一定永远是平方级

看到嵌套循环时，不要机械地认为一定是 $O(n^2)$ 。关键要看每层循环到底执行多少次。

如果外层循环执行 $n$ 次，内层循环每次也执行 $n$ 次，通常是 $O(n^2)$ 。

但如果内层循环每次都把变量翻倍，例如从 1、2、4、8 一直增长到 $n$ ，内层可能是 $O(\log n)$ 。如果外层是 $n$ 次，总复杂度就可能是 $O(n \log n)$ 。

递归复杂度要看调用关系

递归复杂度需要分析两个问题：

递归会调用多少层。
每一层除了递归调用之外还做了多少额外工作。

例如，一个递归函数每次把问题规模减半，并且每层只做常数级工作，常见复杂度可能是 $O(\log n)$ 。

如果每层都要遍历当前规模的数据，同时又把问题拆成多个子问题，复杂度就可能更高。后续学习递归与分治时，会更系统地分析这类情况。

练习：判断双层循环

下面的代码会枚举所有元素对，因此时间复杂度是 $O(n^2)$ 。

void printPairs(const vector<int>& numbers) {
    int n = numbers.size();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << numbers[i] << ", " << numbers[j] << endl;
        }
    }
}

void printPairs(int[] numbers) {
    int n = numbers.length;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println(numbers[i] + ", " + numbers[j]);
        }
    }
}

def print_pairs(numbers):
    n = len(numbers)

    for i in range(n):
        for j in range(n):
            print(numbers[i], numbers[j])

void PrintPairs(int[] numbers)
{
    int n = numbers.Length;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            Console.WriteLine($"{numbers[i]}, {numbers[j]}");
        }
    }
}

外层循环执行 $n$ 次。对于外层的每一次，内层循环又执行 $n$ 次。因此总执行次数大约是 $n^2$ 。

本节小结

分析代码复杂度时，要先明确输入规模和关键操作，再根据顺序结构、循环结构、嵌套结构和递归结构判断增长趋势。

不要只凭代码长短判断效率。短代码也可能很慢，长代码也可能只是常数级操作。真正重要的是关键操作会随着输入规模增长多少次，以及是否额外占用了随规模增长的空间。