波仔
⌨️ 第四章 流程图与算法
📄 一句话概括

大 O 表示法回答一个问题：【数据翻十倍，程序慢多少？】——它扔掉常数与低阶项，只看量级曲线：O(1) 不慌、O(log n) 从容、O(n) 跟着涨、O(n²) 会爆炸——算法选型的一切账都从这张表算起。

📝 本节和前面几节的关系

4-11~4-13 一直在说【O(n²)】【O(n log n)】，这一篇把这两个记号说透。回收 4-13 的归并账（n x log n 的来历）与 4-15 的二分（log n 的代表）。

一、大 O 只看【增长曲线】

定义的白话版：数据规模 n 变大时，操作次数大约跟着哪条曲线涨。三个忽略：

为什么可以这么粗暴：n 小的时候【什么都快】，n 大的时候量级差是天文数字——

规模 O(log n)（二分） O(n)（线性） O(n log n)（快排） O(n²)（冒泡）
10 4 10 33 100
1 000 10 1 000 1 万 100 万
100 万 20 100 万 2 000 万 1 万亿

一百万数据把 O(n²) 和 O(n log n) 拉开约五万倍——这就是【算法比硬件值钱】的账。

二、常见档位一张表（按快到慢）

大 O 名字 代表 n 翻 10 倍时
O(1) 常数 字典取值（3-13）、下标访问 不变
O(log n) 对数 二分查找（4-15）、平衡树（3-17） 多约 3 次操作
O(n) 线性 线性查找、遍历一遍 慢 10 倍
O(n log n) 线性对数 归并、快排、Timsort 慢约 10 倍多一点
O(n²) 平方 冒泡、选择、插入 慢 100 倍
O(2ⁿ) 指数 暴力穷举所有子集 慢 1000 倍

读法：n 翻 10 倍、O(n²) 慢 100 倍、O(2ⁿ) 慢一千多倍——平方往下是工程红线，指数是数据超过 30 就跑不动。

三、复杂度怎么数：看循环嵌套

空间复杂度同款记号量【内存】：归并 O(n)（辅助数组）、快排 O(log n)（递归栈）、原地交换 O(1)。

四、动手 Demo：两档算法的肉眼差距

import time, random

data = [random.randint(0, 9) for _ in range(20000)]
target_sorted = sorted(data)            # Timsort：O(n log n)，Python 内置

def bubble(arr):                        # O(n²)
    a = arr.copy()
    for i in range(len(a) - 1):
        for j in range(len(a) - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

t0 = time.perf_counter(); bubble(data);  t1 = time.perf_counter()
t2 = time.perf_counter(); sorted(data); t3 = time.perf_counter()
print("冒泡:", round(t1 - t0, 3), "秒")
print("Timsort:", round(t3 - t2, 3), "秒")

看到什么算成功（参考量级，机器不同数值不同）：冒泡约 5~15 秒，Timsort 约 0.005 秒——两三千倍的差距，2 万条数据就现形。

读结果：同一份数据、同一台机器，唯一差别是量级（O(n²) vs O(n log n)）。把数据翻到 20 万条，冒泡要按【小时】算、Timsort 仍零点零几秒——曲线不骗人。

五、30 秒实验

跑 import math; print(math.log2(1_000_000))——约 19.93。一百万数据二分只要 20 次——这句背过的话今天用 log2 验了一遍（回收 3-17 的【二十次锁定】）。

六、常见误区

  1. 【大 O 精确等于运行时间】——错。它只讲增长量级：O(n) 的算法常数可能是 O(n²) 的一万倍，n 小的时候后者反而快——量级管大局，常数管小数据。
  2. 【优化常数能救 O(n²)】——救不了。常数优化是【快两三倍】；量级差是【差一万倍】——数据一大必须换算法，调参救不了曲线。
  3. 【只看时间不看空间】——片面。归并 O(n) 辅助内存、动态规划动辄 O(n²) 空间——时间空间是一张表的两列，一起看。
自测三问（点开对答案） 1. **大 O 为什么可以忽略常数和低阶项？** 答：n 大时量级项独大——常数靠硬件改善，低阶项可忽略；量级决定【数据翻倍、耗时怎么涨】这个大局。 2. **一百万数据二分查找大约几次？对应哪个档位？** 答：约 20 次（log2 百万 ≈ 19.9）——O(log n) 档。 3. **为什么说 O(2ⁿ) 实战上等于不可用？** 答：n 翻 10 倍操作涨一千多倍、n 每加 1 翻一倍——数据到三四十个就已经按年计，只配写进【反面教材】。

相关笔记