算法复杂度速查：Big-O、空间复杂度与工程直觉

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

def find_all(nums, target):
    result = []
    for x in nums:            # 外层循环 → O(n)
        if x == target:
            result.append(x)  # 常数操作
    return result             # 总 O(n)

def has_duplicate(nums):
    seen = set()
    for x in nums:            # 每元素 O(1)（哈希）
        if x in seen:
            return True
        seen.add(x)
    return False              # 总 O(n)，不是 O(n²)！

# 用对结构，复杂度天差地别
nums = [3, 1, 4, 1, 5, 9, 2, 6]

# 查 5 次：数组线性 → O(5n)
# 建一次集合再查：O(n) 建 + O(5) 查
seen = set(nums)
print(5 in seen)   # O(1)

线性查找  O(n)       无序数组
二分查找  O(log n)   有序数组（前提：有序！）
哈希查找  O(1) 平均  无序但无范围查询

# 近乎有序数组，插入排序几乎 O(n)
data = sorted([i * 3 % 97 for i in range(1000)])
for i in range(1, len(data)):
    key = data[i]
    j = i - 1
    while j >= 0 and data[j] > key:
        data[j + 1] = data[j]
        j -= 1
    data[j + 1] = key

若 log_b(a) > d   → T(n) = O(n^log_b(a))   分治主导（如矩阵乘）
若 log_b(a) = d   → T(n) = O(n^d · log n)  分层主导（如归并、快排平均）
若 log_b(a) < d   → T(n) = O(n^d)          合并主导（如基于扫描的分治）

# 二分查找递归式：T(n)=T(n/2)+O(1) → O(log n)
def bsearch(arr, lo, hi, target):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return bsearch(arr, mid + 1, hi, target)
    return bsearch(arr, lo, mid - 1, target)

# ArrayList 式扩容：满了就翻倍
class DynArray:
    def __init__(self):
        self.arr = [None] * 1
        self.n = 0

    def append(self, x):
        if self.n == len(self.arr):        # 满了 → 翻倍复制
            self.arr = self.arr + [None] * len(self.arr)
        self.arr[self.n] = x
        self.n += 1

翻倍策略下，复制总代价 = 1 + 2 + 4 + ... + n = 2n - 1
n 次 append 总代价 ≈ 3n → 每次均摊 O(1)

from collections import deque
# 头部插入：deque 是 O(1)，list 是 O(n)
dq = deque(range(100000))
dq.appendleft(999)          # 快
lst = list(range(100000))
lst.insert(0, 999)          # 慢：全部右移

# 方案 A：用集合 → 时间 O(n)，空间 O(n)
def dedup_a(nums):
    return list(set(nums))

# 方案 B：先排序再去重 → 时间 O(n log n)，空间 O(1) 原地
def dedup_b(nums):
    nums.sort()
    return [x for i, x in enumerate(nums) if i == 0 or x != nums[i-1]]

- 缓存（CPU 缓存行 64B）：连续内存访问比跳着访问快 10-100x
- GC：创建大量短命对象 → 停顿；用原地/池化减少分配
- 大输入：O(n²) 空间会直接 OOM——优先流式/分块

算法 A：O(n)   但每步做 100 次操作 → 实际 100n
算法 B：O(n²)  但每步极简、缓存友好  → 实际 0.01n²
交叉点：n = 10000
  n < 10000 → B 更快
  n > 10000 → A 更快

1. 估规模：n 到底多大？（100？10万？1亿？）
2. 算增长：规模翻倍后差距多大？
3. 测真相：用基准（见第 9 节）验证，别猜

# O(n²)：每次拼接复制整个字符串
s = ""
for i in range(100000):
    s += "x"

# O(n)：一次性 join
s = "".join(["x"] * 100000)

# 陷阱：每次循环都排序 → O(n² log n)
for i in range(n):
    window = sorted(arr[i:i+100])   # 100 个元素排序，常数
    # 若窗口随 i 增长 → O(n² log n)

# 正确：一次排序或滑动窗口维护有序结构
data = sorted(arr)

□ 外层循环每层做什么？层层相乘了吗？
□ 内部有没有排序/查找/字符串拼接？
□ 用的集合操作是平均 O(1) 吗？退化条件是什么？
□ 递归的每层工作量 × 深度 = ?

红线示例（单请求 CPU 预算 100ms）：
  n = 1,000,000，目标 O(n) → 约 1-10ms ✓
  同样的 n，若写成 O(n²) → 10¹² 步 → 秒级 ✗

# 简单基准：python 里 timeit
import timeit

def linear(n):
    return sum(range(n))

def quad(n):
    return sum(x * y for x in range(n) for y in range(n))

for n in [1000, 2000, 4000, 8000]:
    t_lin = timeit.timeit(f"linear({n})", globals=globals(), number=10)
    t_quad = timeit.timeit(f"quad({n})", globals=globals(), number=3)
    print(f"n={n}: linear={t_lin:.4f}s quad={t_quad:.4f}s")
# 观察 linear 随 n 线性增长、quad 随 n 平方增长 → 验证复杂度假设

O(1)     → 耗时不变
O(log n) → 耗时微增
O(n)     → 耗时翻倍
O(n log n) → 耗时约 2.1 倍
O(n²)    → 耗时约 4 倍