时间复杂度：程序跑得快不快？

时间复杂度假说：你的程序跑得有多快？

写程序时，除了要让结果正确，另一个重要的问题是：这个程序要跑多久？ 比如，你上传一张照片让电脑识别，如果等了 10 秒才出来，你会觉得还可以；如果等了一整天，那就没法用了。时间复杂度的作用，就是帮你预测：当数据量变大时，程序运行时间会怎么变化。它不会告诉你精确的秒数，但能告诉你“大约要干多少步”。

1. 什么是时间复杂度？

想象一下，老师布置了“找出全班最高的同学”这个任务。如果班上只有 10 个人，你可能只需要看 10 个人就找到了；如果班上有 100 个人，你就需要看 100 个人。人数越多，你花的时间就越多！时间复杂度就是用来描述：当数据量（用字母 N 表示）变大时，程序运行时间会怎么变化。

程序执行的每一句代码、每一次循环，都可以看作完成一个“步骤”。步骤越多，时间越长。我们用一个叫 大 O 表示法 的符号来记录这种关系，比如 O(N)、O(1)、O(N²) 等等。

2. 生活中的比喻：不同复杂度的直观感受

• O(1) —— 翻一本书的目录
  不管书有多厚，你直接翻到想看的那一页，只花 1 步。
  例子：妈妈给你零花钱，每天固定给 10 元，不管星期几。
  程序里：直接从数组下标取一个数 arr[5]，不管数组多大，都花一次操作。

• O(N) —— 全班同学排队找某个人
  从一列队伍里找出叫“小明”的人，需要从第 1 个看到最后 1 个。如果队伍有 N 人，最多看 N 次。
  例子：你有一堆零食，要找出其中过期的那一包，一包一包看。
  程序里：用一个 for 循环遍历整个数组。

• O(N²) —— 全班同学两两握手
  每个人都要和全班其他人握一次手。如果班级有 N 人，总共握手次数 = N × (N-1) / 2，约等于 N²/2。N 增大一点，握手次数暴涨。
  例子：数学老师让每个同学报自己的成绩，再和所有其他同学比一次高低。
  程序里：两层嵌套的 for 循环。

• O(log N) —— 猜数字游戏
  心里想一个 1 到 100 的数字，每次猜大了或小了，直接砍掉一半可能。100 个数字最多猜 7 次（因为 2^7=128 > 100）。即使数字变成 10 万，也只需要猜 17 次左右。
  例子：查字典时，你不会从第一页翻，而是先翻到中间，再根据字母决定往前或往后。
  程序里：二分查找、平衡二叉树的操作。

3. 常见的时间复杂度与代码例子

代码示例：O(N) vs O(1)

下面两个程序都用来计算 1 到 N 的和，但速度完全不同。

// 慢速方法：用循环，运行次数 = N
#include <iostream>
using namespace std;
int main() {
    int N = 100;              // 数据的数量
    int sum = 0;              // 存放总和
    for (int i = 1; i <= N; i++) {
        sum += i;             // 这一步要执行N次
    }
    cout << sum << endl;      // 输出5050
    return 0;
}

// 快速方法：用公式，无论N多大，只算一次
#include <iostream>
using namespace std;
int main() {
    int N = 100;              // 数据的数量
    int sum = N * (N + 1) / 2;   // 只执行1步！
    cout << sum << endl;
    return 0;
}

第一个程序是 O(N)，第二个是 O(1)。当 N=10 万时，第一个要循环 10 万次，第二个一秒就算完。所以，写程序时要尽量选择时间复杂度更小的算法。

4. 怎样判断一段代码的时间复杂度？

• 只看循环：没有循环就是 O(1)；一个循环从 1 到 N 就是 O(N)；两个循环嵌套（外层 N 次，内层也 N 次）就是 O(N²)。
• 循环次数不是简单的 N 时：比如 for (int i = 1; i < N; i = i * 2)，每次 i 翻倍，循环次数是 log₂(N)，所以是 O(log N)。
• 只看次数最多的那部分：如果程序前面有个 O(N) 的循环，后面又有个 O(N²) 的循环，整体就是 O(N²)，因为 N 很大时 N² 远大于 N，次要部分可以忽略。
• 常数系数可以不管：无论循环是 for (int i=0; i<2*N; i++) 还是 for (int i=0; i<100*N; i++)，都是 O(N)，因为常数不影响增长趋势。

小练习：下面的代码运行了多少次？时间复杂度是多少？

int cnt = 0;                    // 记录操作次数
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        cnt++;                  // 这个语句执行 N * N 次
    }
}
cout << cnt << endl;            // 输出 N * N

答案：O(N²)。

5. 新手容易犯的错误

1. 以为 O(1) 永远比 O(N) 快
   不全是。如果 N 很小（比如 N=3），O(N) 的循环只跑 3 次，而有些 O(1) 的复杂计算（比如调用一个超大的数学函数）可能反而更慢。大 O 表示法是看“当 N 很大时”的趋势，小数据时不要迷信复杂度。

2. 忽略常数，但实际场景中常数可能很大
   同样都是 O(N)，一个循环内部执行 10 条语句，另一个只执行 1 条，实际时间可能差 10 倍。不过竞赛和一般分析中，我们更关心趋势。

3. 只考虑最坏情况，忽略平均情况
   例如在数组中查找一个数，如果这个数恰好是第一个，那一次就找到了（最好情况 O(1)）；如果最后一个或者不存在，则需要查完整个数组（最坏 O(N)）。通常我们讨论的是最坏情况，因为它保证了程序的上限时间。

4. 混淆 N 的含义
   有些程序有两个不同的数据规模，比如处理一个 N×M 的矩阵，复杂度可能是 O(N×M)，不能简单说成 O(N²)。

5. 忘记检查隐藏的循环
   比如调用了 C++ 的 sort() 函数，它的内部实现是 O(N log N)，这也算进你程序的时间复杂度里。

6. 完整示例：一个程序展示多种复杂度

下面这个 C++ 程序实现了三个函数，分别对应 O(1)、O(N) 和 O(N²)。你可以自己改变 N 的值，感受它们的耗时差别（注意：N 太大时 O(N²) 会非常慢，建议 N 别超过 5000）。

#include <iostream>
#include <ctime>             // 用来计时
using namespace std;

// 函数1：O(1) —— 直接通过公式计算
void constantTime(int N) {
    int sum = N * (N + 1) / 2;    // 只用1步
    cout << "O(1) 结果: " << sum << endl;
}

// 函数2：O(N) —— 一次循环
void linearTime(int N) {
    int sum = 0;                  // 存放总和
    for (int i = 1; i <= N; i++) {
        sum += i;                 // 执行N次
    }
    cout << "O(N) 结果: " << sum << endl;
}

// 函数3：O(N²) —— 两层循环，计算所有 i*j 的和（只是为了展示复杂度）
void quadraticTime(int N) {
    int total = 0;                // 存放总和
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            total += i * j;       // 执行 N * N 次
        }
    }
    cout << "O(N²) 结果: " << total << endl;
}

int main() {
    int N;                        // 数据的数量
    cout << "请输入一个整数 N: ";
    cin >> N;

    // 分别调用三个函数，并计时（简单起见不精确，但能看出差别）
    constantTime(N);
    linearTime(N);
    quadraticTime(N);

    return 0;
}

运行示例（N=10000 时，O(N²) 会很慢，建议先试 N=1000）：

请输入一个整数 N: 1000
O(1) 结果: 500500
O(N) 结果: 500500
O(N²) 结果: 250500250000

你会看到即使 N=1000，O(N²) 的函数也明显比前两个慢很多。如果 N 变成 10000，O(N²) 可能需要等好几秒甚至更久，而前两个瞬间完成。

7. 小结

时间复杂度就是程序“干活”需要做的步骤数。步骤数越少，程序越快。通常我们会用大 O 表示法，比如 O(1)、O(N)、O(N²) 等来表示。写程序时，要时刻关注数据量 N 有多大，然后选择合适复杂度的算法。如果 N 很大（比如 10⁵ 以上），O(N²) 基本不可用，必须想办法优化到 O(N log N) 或 O(N)。

8. 相关知识点指引

• 空间复杂度：和时间复杂度类似，衡量程序占用的内存有多大。比如开了一个 N×N 的数组，空间复杂度就是 O(N²)。有时候可以用空间换时间（例如把计算结果缓存起来）。
• 算法的稳定性：对于同一种问题，可能有多种算法，它们的复杂度不同。学常见算法（排序、查找、图遍历）时，重点看它们的复杂度。
• 递归中的复杂度：递归函数的时间复杂度可以用“递归树”来分析，比如斐波那契数列的递归是 O(2^N)（非常慢），而用循环则是 O(N)。
• 实际优化技巧：除了降低复杂度，还可以通过减少常数、使用更高效的数据结构（如哈希表、优先队列）来让程序跑得更快。

掌握时间复杂度，你就拿到了编写高效程序的“尚方宝剑”——遇到大任务时，先想想你的程序要跑多久，再决定怎么写。