常见时间复杂度

学习目标

本节整理常见时间复杂度，并通过简单例子理解它们的增长差异。

学习数据结构时，不需要一开始记住所有复杂数学形式，但必须熟悉最常见的几类： $O(1)$ 、 $O(\log n)$ 、 $O(n)$ 、 $O(n \log n)$ 、 $O(n^2)$ 。

常数时间复杂度记为 $O(1)$ 。它表示操作次数不随输入规模增长而增长。

例如，通过下标访问数组中的一个元素，通常可以看作 $O(1)$ ：

int first = numbers[0];

int first = numbers[0];

first = numbers[0]

int first = numbers[0];

这里不管数组有 10 个元素还是 100 万个元素，访问第一个元素的动作本身都不需要从头遍历到尾。

对数时间复杂度通常记为 $O(\log n)$ 。它常见于每一步都能排除大量候选范围的问题。

二分查找就是典型例子。前提是数据已经有序，每次比较中间元素后，都可以排除一半范围。

如果有 16 个元素，最多大约缩小 4 次；如果有 1024 个元素，最多大约缩小 10 次。这种增长非常慢。

对数复杂度的核心特征是：输入规模成倍增加时，操作次数只增加少量。

线性时间复杂度记为 $O(n)$ 。它表示操作次数和输入规模大致成正比。

遍历数组、顺序查找、统计列表中所有元素的和，通常都是 $O(n)$ ：

int sum = 0;

for (int number : numbers) {
    sum += number;
}

int sum = 0;

for (int number : numbers) {
    sum += number;
}

total = 0

for number in numbers:
    total += number

int sum = 0;

foreach (int number in numbers)
{
    sum += number;
}

这里必须访问每个元素一次。如果元素数量翻倍，循环次数也大约翻倍。

线性对数时间复杂度记为 $O(n \log n)$ 。它常见于高效排序算法，例如归并排序、堆排序以及许多语言库中的通用排序实现。

可以粗略理解为：算法需要处理所有 $n$ 个元素，同时还包含不断拆分或合并的对数层级。

$O(n \log n)$ 通常比 $O(n^2)$ 更适合较大规模排序问题，也是很多排序算法追求的重要复杂度级别。

平方时间复杂度记为 $O(n^2)$ 。它常见于两层都与输入规模 $n$ 有关的嵌套循环。

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

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

for i in range(n):
    for j in range(n):
        print(i, j)

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

外层循环执行 $n$ 次，内层循环每次也执行 $n$ 次，总次数大约是：

n \times n = n^2

所以复杂度是 $O(n^2)$ 。

从增长较慢到增长较快，常见复杂度通常可以这样排列：

O(1) < O(log n) < O(n) < O(n log n) < O(n^2)

这个顺序不是为了死记硬背，而是帮助你建立直觉：当数据规模变大时，平方级增长往往会比线性级增长快得多，对数级增长则非常慢。

常见时间复杂度反映了不同算法随输入规模增长的速度差异。

$O(1)$ 表示固定成本， $O(\log n)$ 表示每次大幅缩小范围， $O(n)$ 表示逐个处理， $O(n \log n)$ 常见于高效排序， $O(n^2)$ 常见于双层规模相关循环。后续学习数据结构时，这些复杂度会反复出现。