FAQ 2: 关于“复杂度”¶

时间复杂度（Time Complexity）¶

时间复杂度表示算法运行所需要的时间与输入数据量之间的关系，用大写字母 O 来表示，比如 O(1)、O(n)、O(n^2) 等。

常见例子：

// 例1：O(1) 常数时间
int a = 10;
int b = 20;
int c = a + b;

这段代码只执行一次加法，所以时间复杂度是 O(1)。

// 例2：O(n) 线性时间
for (int i = 0; i < n; i++) {
    printf("%d\n", i);
}

这段代码执行了 n 次操作，时间复杂度是 O(n)。

// 例3：O(n^2) 平方时间
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        printf("(%d, %d)\n", i, j);
        printf("%d\n", i + j);
    }
}

嵌套两个循环，每个跑 n 次，总共跑了 n×n 次，是 O(n²)。

// 例3：O(n^2) 平方时间
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        printf("(%d, %d)\n", i, j);
        printf("%d\n", i + j);
    }
}

嵌套两个循环，总共要跑约 n²/2 次，也是 O(n²)。

空间复杂度（Space Complexity）¶

类似地，空间复杂度表示算法运行时占用的内存空间与输入数据量之间的关系。

例子：

// 例1：O(1) 空间
int a = 5;
int b = 10;

这里只用了两个变量，占用常数空间，空间复杂度是 O(1)。

// 例2：O(n) 空间
int arr[n]; // 定义了一个长度为 n 的数组

数组 arr 需要 n 个存储单元，所以是 O(n) 的空间复杂度。

复杂度表达中的“近似”¶

在使用大O符号表示时间复杂度时，我们只关心增长速度最快的项，忽略常数和低阶项，同样也忽略前面的系数。

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        printf("(%d, %d)\n", i, j);
    }
}

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        printf("%d\n", i + j);
    }
}

for (int k = 0; k < n; k++) {
    printf("%d\n", k);
}

上面一共有 3 部分： - 第一、二个嵌套循环执行了 n² 次（O(n²)） - 第三个循环分别执行了 n 次（O(n)）

总执行次数是 2n² + n，但我们写复杂度时只保留最大项 n²，而且忽略前面的系数 2，所以时间复杂度是：O(n²)。这就像：10000 + 100，主要是“10000”在起作用，小的项可以忽略。

备注¶

常见时间复杂度等级（从快到慢）：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
一般来说，O(n log n) 是很多高效排序算法的时间复杂度，比如 quicksort（快速排序）。
O(2ⁿ) 和 O(n!) 增长非常快，处理大数据时几乎不可用。