数学重学 - 14 函数增长与大O

数学重学
,

这是 数学重学路线图 阶段三的子页面

📌 相关笔记：函数与图像

函数增长与大O记号

为什么要学这个？

选错数据结构或算法，数据量小的时候看不出区别

一旦数据量上去（百万、千万、上亿），系统直接崩掉

面试必考，工作中做技术选型的核心依据

真实场景：你用了 O(n²) 的算法处理100万条日志，要跑11.5天；换成 O(n log n) 只要20秒

大O 不是学院派玩具，它是工程师的生存工具

核心概念：什么是大O？

一句话：大O描述的是”当输入规模 n 趋向无穷时，算法运行时间的增长趋势”

直觉比喻：

你有一堆快递要送，O(1) = 无人机直投（不管多少件都一次搞定）

O(n) = 骑电动车一件件送

O(n²) = 每送一件都要回仓库重新找一遍

O(2^n) = 每增加一件快递，工作量翻倍

核心思想：忽略常数和低阶项，只关心增长的速度

3n² + 5n + 100 → O(n²)

1000n → O(n)，虽然常数大但增长慢

0.001 × 2^n → O(2^n)，常数再小指数增长也吓人

常见复杂度排序

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

从左到右，增长越来越快，算法越来越慢

直觉理解：n = 1,000,000 时的操作次数

1
2
3
4
5
6
7
8
9
| 复杂度       | 操作次数            | 直觉感受               | 典型场景        |
|-------------|--------------------|-----------------------|----------------|
| O(1)        | 1                  | 一瞬间                 | 哈希表查找      |
| O(log n)    | 20                 | 眨个眼                 | 二分查找        |
| O(n)        | 1,000,000          | 几秒钟                 | 遍历数组        |
| O(n log n)  | 20,000,000         | 十几秒                 | 排序(归并/快排)  |
| O(n²)       | 1,000,000,000,000  | 好几天                 | 嵌套循环        |
| O(2^n)      | 10^301029          | 宇宙毁灭也算不完        | 暴力枚举子集     |
| O(n!)       | 更大               | 别想了                 | 暴力枚举全排列   |

关键洞察：O(n²) 和 O(n log n) 看起来只差一点，但在百万级数据上差了 50000 倍

大O 的数学定义（简化版）

f(n) = O(g(n)) 意思是：存在常数 C 和 n₀，当 n > n₀ 时，f(n) ≤ C × g(n)

翻译：f(n) 的增长速度不会超过 g(n)（忽略常数倍）

例子：

3n² + 5n + 100 = O(n²)，因为当 n 够大时，3n² + 5n + 100 ≤ 4n²

100n = O(n²) 也成立（上界可以松一点），但我们一般取最紧的上界

相关记号：

Ω(n²)：下界，至少这么慢

Θ(n²)：紧界，就是这么快/慢

日常口语中说的”复杂度是 O(n²)”通常指的是 Θ(n²)

常见数据结构操作复杂度表

1
2
3
4
5
6
7
8
9
| 数据结构       | 查找      | 插入      | 删除      | 备注                    |
|---------------|----------|----------|----------|------------------------|
| 数组(有序)     | O(log n) | O(n)     | O(n)     | 二分查找，插入要移动元素   |
| 数组(无序)     | O(n)     | O(1)     | O(n)     | 追加快，查找慢            |
| 链表           | O(n)     | O(1)     | O(1)     | 知道位置的话插删很快       |
| 哈希表         | O(1)平均  | O(1)平均  | O(1)平均  | 最坏O(n)，但很少发生      |
| 二叉搜索树BST  | O(log n) | O(log n) | O(log n) | 平衡时；退化成链表就O(n)  |
| 堆             | O(n)     | O(log n) | O(log n) | 查找慢，但找最大/最小O(1) |
| B+树           | O(log n) | O(log n) | O(log n) | 磁盘友好，数据库索引首选   |

如何分析代码复杂度

规则1：单层循环 → O(n)

1
2
3
for i in range(n):    # O(n)
do_something()    # O(1)
# 总体 O(n)

规则2：嵌套循环 → 相乘

1
2
3
4
for i in range(n):        # O(n)
for j in range(n):    # O(n)
    do_something()    # O(1)
# 总体 O(n) × O(n) = O(n²)

规则3：顺序执行 → 取最大

1
2
3
4
5
6
for i in range(n):        # O(n)
do_something()
for i in range(n):        # O(n)
for j in range(n):    # O(n)
    do_something()
# O(n) + O(n²) = O(n²)，取较大的

规则4：循环内做二分 → O(n log n)

1
2
3
for i in range(n):              # O(n)
binary_search(arr, target)  # O(log n)
# 总体 O(n log n)

规则5：递归用主定理

T(n) = aT(n/b) + O(n^d)

如果 d > log_b(a)：O(n^d)

如果 d = log_b(a)：O(n^d × log n)

如果 d < log_b(a)：O(n^(log_b(a)))

归并排序：T(n) = 2T(n/2) + O(n) → a=2, b=2, d=1 → d=log₂2=1 → O(n log n)

规则6：循环变量每次翻倍/减半 → O(log n)

1
2
3
4
i = 1
while i < n:
i *= 2    # 每次翻倍，log₂n 次就到 n
# O(log n)

后端应用

为什么 MySQL 索引用 B+树 (O(log n)) 不用链表 (O(n))？

1000万条记录：B+树查找约 3-4 次磁盘IO，链表平均 500万次

数据库最怕磁盘IO，B+树的矮胖结构（高扇出）把高度压到极低

为什么 Redis 有序集合用跳表不用红黑树？

两者查找都是 O(log n)

跳表实现更简单、范围查询更方便、并发友好

API 分页设计：

OFFSET 分页：越往后越慢 O(offset + limit)

游标分页：始终 O(limit)，利用索引

缓存：把 O(n) 的数据库查询变成 O(1) 的缓存命中

大数据应用

MapReduce 为什么能处理 PB 级数据？

单机排序 1TB：O(n log n)，但 n 太大内存放不下

1000台机器各排序 1GB：每台 O(n/k × log(n/k))，然后归并

分治思想把不可能变成可能

分布式排序：外部排序的复杂度 = O(n log n) 但实际瓶颈在 IO

Spark 的 Shuffle：本质是分布式的 O(n) 数据重分布

安全应用

暴力破解复杂度：

8位纯数字密码：10^8 = 1亿种，O(10^8)，几分钟就破

8位大小写+数字+特殊字符：95^8 ≈ 6.6×10^15，O(10^15)，要好几年

这就是为什么密码要求复杂度

bcrypt 故意设计慢：

MD5 哈希一个密码：微秒级

bcrypt（cost=12）：约 250ms

暴力破解从”几小时”变成”几百年”

密码学安全依赖计算复杂度：

RSA 安全性基于大数分解的困难（目前没有多项式时间算法）

AES-128：暴力 2^128 ≈ 3.4×10^38 次，人类算力不够

Python 代码：实测不同复杂度的运行时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import time
import math
import random

def measure_time(func, *args):
"""测量函数运行时间"""
start = time.perf_counter()
result = func(*args)
end = time.perf_counter()
return end - start, result

# O(1) - 哈希表查找
def o_1_lookup(data_dict, key):
return data_dict.get(key)

# O(log n) - 二分查找
def o_logn_binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
return -1

# O(n) - 线性遍历
def o_n_linear_search(arr, target):
for i, v in enumerate(arr):
    if v == target:
        return i
return -1

# O(n log n) - 排序
def o_nlogn_sort(arr):
return sorted(arr)

# O(n²) - 冒泡排序
def o_n2_bubble_sort(arr):
arr = arr.copy()
n = len(arr)
for i in range(n):
    for j in range(0, n - i - 1):
        if arr[j] > arr[j + 1]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr

# ========== 对比测试 ==========
sizes = [1000, 5000, 10000, 50000]

print(f"{'n':>8} | {'O(1)':>10} | {'O(log n)':>10} | {'O(n)':>10} | {'O(n log n)':>12} | {'O(n²)':>10}")
print("-" * 75)

for n in sizes:
arr = list(range(n))
data_dict = {i: i for i in range(n)}
target = n - 1  # 最坏情况

t1, _ = measure_time(o_1_lookup, data_dict, target)
t2, _ = measure_time(o_logn_binary_search, arr, target)
t3, _ = measure_time(o_n_linear_search, arr, target)
t4, _ = measure_time(o_nlogn_sort, random.sample(range(n), n))
t5, _ = measure_time(o_n2_bubble_sort, random.sample(range(min(n, 10000)), min(n, 10000)))

print(f"{n:>8} | {t1:>10.6f} | {t2:>10.6f} | {t3:>10.6f} | {t4:>12.6f} | {t5:>10.6f}")

Python 代码：增长曲线可视化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import matplotlib.pyplot as plt
import numpy as np

n = np.arange(1, 101)

plt.figure(figsize=(12, 8))
plt.plot(n, np.ones_like(n), label='O(1)', linewidth=2)
plt.plot(n, np.log2(n), label='O(log n)', linewidth=2)
plt.plot(n, n, label='O(n)', linewidth=2)
plt.plot(n, n * np.log2(n), label='O(n log n)', linewidth=2)
plt.plot(n, n ** 2, label='O(n²)', linewidth=2)
# O(2^n) 增长太快，只画前20个
n_small = np.arange(1, 21)
plt.plot(n_small, 2.0 ** n_small, label='O(2^n)', linewidth=2, linestyle='--')

plt.xlabel('输入规模 n', fontsize=14)
plt.ylabel('操作次数', fontsize=14)
plt.title('不同复杂度的增长曲线对比', fontsize=16)
plt.legend(fontsize=12)
plt.ylim(0, 5000)
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('complexity_comparison.png', dpi=150)
plt.show()
print("图表已保存")

常见误区

误区1：O(n) 一定比 O(n²) 快

错！O(100n) 在 n < 100 时比 O(n²) 慢

大O是渐近分析，小数据量常数项也重要

误区2：大O就是运行时间

大O描述的是增长率，不是绝对时间

同样 O(n) 的算法，一个可能比另一个快10倍

误区3：空间复杂度不重要

很多时候空间比时间更关键（内存有限、缓存局部性）

例如：归并排序 O(n) 额外空间 vs 快排 O(log n) 额外空间

误区4：最坏情况就是实际情况

快排最坏 O(n²)，但平均 O(n log n)，实际中非常快

哈希表最坏 O(n)，但平均 O(1)

练习题

练习1：分析以下代码的时间复杂度

1
2
3
4
5
6
7
8
def mystery(n):
count = 0
i = 1
while i < n:
    for j in range(n):
        count += 1
    i *= 2
return count

答案：外层 while 循环 i 每次翻倍 → O(log n) 次，内层 for 循环 O(n)，总共 O(n log n)

练习2：一个数据库表有5000万条记录，用B+树索引查找一条记录大约需要几次磁盘IO？

答案：log₂(50000000) ≈ 25.5，但B+树每个节点有几百个key（假设扇出500），所以高度 ≈ log₅₀₀(50000000) ≈ 3 层。约 3-4 次磁盘IO。

练习3：你的API响应时间随用户数线性增长，当1000用户时响应50ms，10万用户时预期多少？

答案：线性增长 O(n)，用户数增长100倍，响应时间也增长100倍 → 50ms × 100 = 5000ms = 5秒。这已经不可接受了，需要优化（缓存、索引、分库分表）。

练习4：为什么说”密码每多一位，暴力破解难度就指数增长”？

答案：假设每位有 k 种可能字符。n 位密码总组合 = k^n。每多一位乘以 k，这是指数增长 O(k^n)。比如 k=62（大小写+数字），8位有 2.18×10^14 种，9位有 1.35×10^16 种，多一位就多62倍。

练习5：以下操作分别是什么复杂度？

(a) Python 的 list.append(x) → 答案：平摊 O(1)

(b) Python 的 list.insert(0, x) → 答案：O(n)，所有元素要后移

(c) Python 的 x in set_obj → 答案：平均 O(1)，哈希查找

(d) Python 的 x in list_obj → 答案：O(n)，线性查找

(e) sorted(list_obj) → 答案：O(n log n)，Timsort

上一章 目录 下一章
13-排列组合与计数 数学重学路线图 15-求和公式与级数