算法快慢：为什么不能只看跑得顺不顺

同样的任务，不同算法可能差出天壤之别。数据少时看不出来：100 个数怎么排都快；数据一大（比如十万、百万），算法的差距立刻暴露。复杂度就是用来"预测"算法在大数据下表现的数学工具。

竞赛里有一句老话："算法对不对决定能不能得分，复杂度够不够决定能不能过数据。"学复杂度，是从"会写程序"走向"会写高效程序"的第一步。

复杂度不是考试名词，是程序员的生存技能。
本文核心知识点
  • 时间操作次数随数据增长。
  • 大 O描述增长量级。
  • 排序O(n²) 与 O(n log n)。
  • 空间内存同样重要。
算法复杂度配图：蓝色渐变背景中央一架银色天平，左托盘放小方块积木、右托盘放大方块积木，天平向右侧倾斜，背景左右有蓝色阶梯，右侧阶梯顶端有一颗发光黄色五角星，天平右下角有一个装着黄色沙子的沙漏
复杂度像天平：数据越大，算法差距越明显。

时间复杂度：操作次数说了算

时间复杂度不看"跑了几秒"（机器不同结果不同），而看"基本操作做了多少次"。比如一个循环跑 n 次，操作次数就是 n；两个嵌套循环各跑 n 次，操作次数就是 n×n。

for i in range(n):        # n 次
    print(i)

for i in range(n):        # n*n 次
    for j in range(n):
        print(i, j)

数据规模用 n 表示，操作次数是 n 的函数，这就是时间复杂度的基础。

大 O 记号：用"量级"说话

操作次数是 3n+5 还是 2n+100，在 n 很大的时候没区别，都是"线性增长"。大 O 记号只保留最高阶、去掉常数：3n+5 → O(n)，n²+n → O(n²)。

def linear(n):      # O(n)
    for i in range(n):
        pass

def quadratic(n):   # O(n^2)
    for i in range(n):
        for j in range(n):
            pass

记法规则就两条：丢常数、留最高阶。学会这个，就能给任何循环数复杂度。

常见复杂度排序

按增长速度从慢到快，常见的有：O(1) 常数（查一个变量）、O(log n) 对数（二分查找）、O(n) 线性（遍历一遍）、O(n log n)（快排归并）、O(n²) 平方（冒泡选择）、O(2ⁿ) 指数（暴力枚举全部子集）。

记住关键数字：n=100 时 n² 是一万次没问题，n=100000 时 n² 是一百亿次直接超时，但 n log n 只有约一百七十万次——这就是竞赛里"十万数据必须用 O(n log n)"的原因。

空间复杂度：内存也要算账

除了时间，还要算内存：额外开了多大的数组、字典、递归栈，就是空间复杂度。规则和时间一样：数主要变量的大小。

def copy_list(a):      # O(n) 空间
    b = []
    for x in a:
        b.append(x)
    return b

竞赛里常见约束：内存 256MB，n=100000 的 int 数组（约 40 万字节级别）没问题，但要小心二维表 n² 可能爆内存。时间不够或空间不够都过不了题。