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

你有没有遇到过这种情况：打开一个游戏，加载了半分钟还没进去；或者运行一个程序，等了好久才出结果。程序跑得快不快，关键看它处理数据的速度。时间复杂度就是用来衡量程序运行时间如何随着数据量的增加而增长的。就像你写作业的时间会随着题目数量变化一样——5道题可能10分钟，50道题就要100分钟，这背后都有一个“增长规律”。

1. 什么是“大O表示法”？

想象一下老师布置了 n 道数学题。如果你每道题用1分钟，那么完成所有作业的时间就是 n 分钟。如果 n 变成两倍（比如从10道变成20道），时间也变成两倍（从10分钟变成20分钟）。这种“正比关系”在编程里叫做 O(n)，读作“大O n”。这里的“O”表示“阶”（order），它只看增长趋势，不看具体数字。

再举一个生活例子：你有一袋零食，要分给排队的 n 个小朋友，每人一颗糖。你要一颗一颗地拿，拿的次数就是 n。如果小朋友人数翻倍，拿的次数也翻倍。这就是O(n)的操作。

但如果你用的是笨办法：每拿一颗糖，都要和前面所有小朋友的名字比较一遍，看看他是不是已经拿过了（防止重复发糖）。那你就得比较 1 + 2 + 3 + ... + n 次，总数大约是 n × n 的一半，也就是 n² 量级。这种算法记作 O(n²)。当 n 很大时（比如200个小朋友），比较次数就变成约 40000次，慢得像蜗牛。

2. 常见的几种时间复杂度

O(1) —— 常数时间
不管数据量多大，操作次数都固定。比如你从抽屉里拿第一支笔，无论抽屉里有多少支笔，你拿一支的时间都一样。
代码例子：直接计算1到n的和，用公式 n*(n+1)//2，只做一次运算。
```
# 用数学公式直接求和，时间复杂度 O(1)
def sum_fast(n):
    result = n * (n + 1) // 2  # 一步算出总和
    return result

print(sum_fast(1000000))  # 一秒就出结果
```

O(n) —— 线性时间
操作次数和数据量成正比。比如你检查全班每个人的作业是否交齐，每个人看一遍。
原来的求和代码就是O(n)：

# 用循环求和，每加一次做一步，总共 n 步
def sum_slow(n):
    total = 0
    for i in range(1, n + 1):
        total += i  # 执行 n 次
    return total

print(sum_slow(1000000))  # 需要等一会儿

O(n²) —— 平方时间
双重循环，比如打印一个 n × n 的表格。
生活例子：你有一个朋友列表，想给每个人发消息，但发之前要和列表里所有人确认是否已经发过——这样每人都要问一遍其他人，总共 n² 次询问。
代码例子：
```
# 双重循环，外层 n 次，内层 n 次，总共 n² 次操作
n = 5
for i in range(n):
    for j in range(n):
        print(f"({i}, {j})", end=" ")
    print()  # 换行
```
O(log n) —— 对数时间（拓展知识）
像猜数字游戏：从1到100猜一个数，每次猜中间的数，能排除一半。100个数最多猜7次（log₂100≈7）。即使数字变成100万，也只要猜20次左右。这就是二分查找的效率。
常见于二分查找、平衡树等算法。

3. 新手容易犯的错误

只看循环个数，忽略内层循环的变量
例如下面这个代码，内层循环的次数是 n - i，总和是 n + (n-1) + ... + 1 = n(n+1)/2，它还是 O(n²)，不是O(n)。因为随着 n 变大，平方项主导。
```
# 看似只有一层，实际上是平方复杂度
n = 100
total = 0
for i in range(n):
    for j in range(i, n):  # 内层从 i 开始
        total += 1
print(total)  # 结果是 5050，约 n²/2
```
把常数误认为影响趋势
O(100n) 还是 O(n)，因为当 n 很大时，100倍只是常数，不影响增长趋势。同样，O(0.5n²) 还是 O(n²)。时间复杂度只看“最大增长项”，忽略常数系数。
假设所有循环都是 O(n)
例如在循环里又调用了另一个 O(n) 的函数，那总复杂度就是 O(n²)。要看清每一步操作的成本。

4. 完整可运行的代码示例：比较三种求和方法

下面代码用不同的方法计算从1到n的和，并输出运行时间（实际时间受机器影响，但趋势能看出来）。

import time

# 方法1：直接公式 O(1)
def sum_formula(n):
    return n * (n + 1) // 2

# 方法2：循环累加 O(n)
def sum_loop(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

# 方法3：双重循环 O(n²)
def sum_double_loop(n):
    total = 0
    for i in range(1, n + 1):
        for j in range(1, i + 1):
            total += 1  # 每次加1，最后等于 i
    return total

# 测试 n = 10000
n = 10000

start = time.time()
result1 = sum_formula(n)
end = time.time()
print(f"O(1) 公式: {result1}, 耗时 {end-start:.6f} 秒")

start = time.time()
result2 = sum_loop(n)
end = time.time()
print(f"O(n) 循环: {result2}, 耗时 {end-start:.6f} 秒")

start = time.time()
result3 = sum_double_loop(n)
end = time.time()
print(f"O(n²) 双重循环: {result3}, 耗时 {end-start:.6f} 秒")

运行结果（可能因机器不同有差异）：

O(1) 公式: 50005000, 耗时 0.000002 秒
O(n) 循环: 50005000, 耗时 0.0003 秒
O(n²) 双重循环: 50005000, 耗时 0.15 秒

可以看到，当n=10000时，O(n²)已经慢了几百倍，而O(1)几乎瞬间完成。

5. 相关指引

现在你已经了解了时间复杂度是怎么回事。接下来可以继续学习：

空间复杂度：程序运行需要多少额外内存，和时间复杂度像一对兄弟。
常见算法复杂度：比如冒泡排序是O(n²)，快速排序是O(n log n)，查找无序列表是O(n)，有序列表二分查找是O(log n)。
如何优化代码：把O(n²)变成O(n log n)或O(n)，是程序员的重要技能。

试试判断下面代码的时间复杂度吧：

# 这段代码在做什么？
def mystery(lst):
    result = []
    for num in lst:
        if num % 2 == 0:   # 如果是偶数
            result.append(num * 2)
    return result

答案：这个函数遍历了一遍列表，每次操作是常数时间，所以是 O(n)，其中n是列表长度。