w wyl123ly 的博客
MD

算法-复杂度分析

53 KB 2026.10.11 原文件

算法-复杂度分析

一句话概括

复杂度分析(Complexity Analysis) 是一套「不运行代码就能预估资源消耗」的数学工具。它回答两个问题:这段代码随输入规模 变大,时间会涨多快?内存会涨多快?

本篇覆盖:大 / / 的形式化定义、常见增长曲线与具体耗时估算、最好/最坏/平均情况、均摊分析(聚合法)、递归分析三件套(递归树、代入法、主定理)、空间复杂度与递归栈、算法复杂度速查表、P 与 NP、工程中的性能估算方法。

这是全库最重要的基础篇之一——后面每一篇算法笔记的结论都建立在这里的记号之上。

是什么

三种渐进记号

设 、 是定义在正整数上的函数(通常是算法的「基本操作次数」)。

形式化定义

大 (渐进上界):存在常数 与 ,使得对所有 都有 。记作

大 (渐进下界):存在常数 与 ,使得对所有 都有 。记作

大 (渐进紧确界): 且 ,即存在 与 ,使得

记作 。

另有小 (严格上界):对任意 都存在 ;例如 ,但 。

三者的直观区别

记号读法类比例子
「不超过」,也
「不少于」,也
「恰好是」,唯一确定的那个
「严格小于」

别把 当成「精确值」

归并排序说 ,说 在数学上也没错(因为它确实不超过 量级),只是不紧。

工程上我们默认用 表达紧确上界,即想说的是 。

「渐进」两个字的含义

复杂度分析牺牲了三样东西,换来「与机器无关」:

  1. 忽略常数因子: 和 都写作
  2. 忽略低阶项: 写作
  3. 只关心 : 时 可能真的比 快

为什么忽略常数是对的

常数因子受语言、编译器、CPU 影响极大(Python 循环比 C 慢 50 倍),但增长趋势不会变。

当 从 涨到 (1000 倍), 涨约 2000 倍, 涨 1000000 倍。

无论常数多小, 足够大时低阶算法一定输——这就是渐进的威力。

为什么需要它

「跑一遍计时」的五个致命缺陷

import time

def f(n):
    s = 0
    for i in range(n):
        s += i
    return s

start = time.perf_counter()
f(1_000_000)
print(f"耗时 {time.perf_counter() - start:.4f} 秒")

这种方法叫 benchmark(基准测试),它有价值,但不能替代复杂度分析:

缺陷说明具体后果
① 依赖硬件同一份代码在 M3 笔记本和十年前的服务器上差 10 倍结论无法跨机器复用
② 依赖语言与实现Python 的循环比 C 慢约 50 倍,PyPy 又比 CPython 快 4 倍换个解释器结论就翻转
③ 只能测已写完的代码设计阶段就要判断方案可行性写完才发现超时,白干
④ 测不到最坏情况随机数据往往比最坏数据快得多上线后被恶意输入打挂(哈希碰撞攻击就是典型)
⑤ 测不到 很大的情况无法真的跑 无法预测规模增长后的表现

复杂度分析的核心价值

它是唯一能在「代码还没写」时回答「 能不能在 1 秒内跑完」的工具。

一个经验法则: 在 时是 次操作,任何语言都救不了。

复杂度分析的三个层次

  1. 粗估:判断 还是 ,决定算法选型
  2. 精确:算出具体操作次数,指导常数优化
  3. 实测:用 timeit 验证,确认没有隐藏的常数爆炸(如 Python 中 list.insert(0, x) 是 )

核心内容

一、常见复杂度增长曲线

复杂度名称典型算法
常数1111数组下标访问、哈希查找
对数3.36.61020二分查找、平衡树查找
根号3.210321000试除法判素数、分块
线性10100一次遍历、计数排序
线性对数33664归并/快速/堆排序
平方100冒泡排序、朴素最短路
立方Floyd、矩阵乘法
指数1024天文数字不可能枚举子集、朴素背包
阶乘不可能不可能全排列、TSP 暴力

时到底要多久

假设一次基本操作耗时 1 纳秒( 秒)——这是现代 CPU 单条简单指令的量级,已经相当乐观:

复杂度 的操作次数耗时直观感受
1 毫秒无感
20 毫秒无感
1 秒勉强
约 16.7 分钟无法接受
约 31.7 年永远等不到
远超宇宙年龄数学上都不可能

竞赛与工程的经验阈值

以「1 秒内完成 次基本操作」为基准(C++ 水平,Python 约 ):

| 数据规模 | 可接受的复杂度 |

|---|---|

| | 、 |

| | 、状压 DP |

| | |

| | |

| | 、 |

| | |

| | 、 |

看到题目给的 范围,基本就能反推应该用什么算法——这是最有用的实战技巧。

"""实测:不同复杂度的实际增长(用少量数据外推,验证理论结论)。

运行前请把 n 调小,否则 O(n^2) 那一行会让你等很久。
"""
import time
import math


def timeit(fn, *args, repeat=3):
    """返回最快一次耗时(秒)。取最小值可减少系统调度噪声。"""
    best = float("inf")
    for _ in range(repeat):
        start = time.perf_counter()
        fn(*args)
        best = min(best, time.perf_counter() - start)
    return best


def f_const(n):
    return 42


def f_log(n):
    c = 0
    while n > 1:
        n //= 2          # 每次规模减半 -> 循环 log2(n) 次
        c += 1
    return c


def f_linear(n):
    s = 0
    for i in range(n):
        s += i
    return s


def f_nlogn(n):
    # 模拟 n log n:外层 n 次,内层 log n 次
    s = 0
    for i in range(n):
        j = n
        while j > 1:
            j //= 2
            s += 1
    return s


def f_quadratic(n):
    s = 0
    for i in range(n):
        for j in range(n):
            s += 1
    return s


if __name__ == "__main__":
    for n in (1000, 2000, 4000):
        print(
            f"n={n:5d}  "
            f"O(1)={timeit(f_const, n):.2e}s  "
            f"O(log n)={timeit(f_log, n):.2e}s  "
            f"O(n)={timeit(f_linear, n):.2e}s  "
            f"O(n log n)={timeit(f_nlogn, n):.2e}s  "
            f"O(n^2)={timeit(f_quadratic, n):.2e}s"
        )
    # 观察规律:n 翻倍时,O(n) 耗时翻倍,O(n log n) 略多于翻倍,
    # O(n^2) 耗时变成 4 倍 —— 这就是"增长趋势与机器无关"的直接证据。

二、最好、最坏与平均情况

以快速排序(Quick Sort)的 partition 为例,输入规模 。

情况触发条件递推式结果说明
最好每次划分都均分基准恰好是中位数
平均随机数据随机化后以极高概率均分
最坏每次划分都分成 和 已排序数组 + 首元素作基准

三种情况的定义与用途
情况定义用途
最好情况(Best Case)所有输入中代价最小的那个意义最小,仅用于说明「至少不会更差」
最坏情况(Worst Case)所有输入中代价最大的那个最重要:给系统性能上界,是 SLA 与实时系统的依据
平均情况(Average Case)在输入分布上的期望代价反映日常体验,但依赖「输入分布」假设

「平均情况」的陷阱

平均情况的结论依赖你假设的输入分布。如果快排假设「所有排列等概率」,那么平均是 ;

但真实数据常常接近有序,固定取首元素作基准就退化成最坏情况。

这就是为什么工程实现要随机化基准或三数取中——它把「输入分布」变成「由算法自己控制的随机性」。

如何选择分析哪种情况

- 写基础库 / 面向不可信输入 → 看最坏情况(要防恶意构造)

- 做数据分析、离线批处理 → 看平均情况

- 需要硬实时保证(如自动驾驶、交易所撮合) → 必须看最坏情况

三、均摊分析(Amortized Analysis)

均摊复杂度研究的不是「单次操作」而是「一串操作序列的总代价平摊到每次」。

均摊 ≠ 平均

平均情况分析要对输入的概率分布做假设;

均摊分析不对输入做任何概率假设,它是对任意操作序列的最坏情况总代价求平均。

换句话说:均摊是确定的保证,不是统计期望。

例子 1:动态数组(list.append)

Python 的 list 底层是动态数组(dynamic array)。容量满时扩容:

Python 的实际策略(CPython list_resize):新容量取

即大约按 增长;其他语言常用 (如 C++ std::vector 的部分实现)或 (如 Java 的 ArrayList)。

聚合法(Aggregate Method) 分析(假设扩容 2 倍,从容量 1 开始):

第 次 append是否扩容本次拷贝代价
1是(1→2)1
2是(2→4)2
3否1
4是(4→8)4
5,6,7否1,1,1
8是(8→16)8

次 append 的总代价:

结论:list.append 的均摊复杂度是 ,但单次最坏是 。

如果扩容策略是「每次加 1」

那样每次 append 都要拷贝整个数组, 次总代价是 ,均摊 。

成倍扩容是均摊 的关键——这解释了为什么所有标准库都这么写。

"""实现一个动态数组,统计扩容次数与总拷贝元素数,验证均摊 O(1)。"""


class DynamicArray:
    def __init__(self, growth=2):
        self._data = [None] * 1      # 初始容量 1
        self._size = 0
        self._cap = 1
        self._growth = growth
        self.total_copies = 0        # 累计拷贝的元素个数(用于验证均摊)

    def append(self, x):
        if self._size == self._cap:
            self._resize(self._cap * self._growth)
        self._data[self._size] = x
        self._size += 1

    def _resize(self, new_cap):
        new_data = [None] * new_cap
        for i in range(self._size):
            new_data[i] = self._data[i]
        self.total_copies += self._size     # 记录这次搬了多少个元素
        self._data = new_data
        self._cap = new_cap

    def __len__(self):
        return self._size


def verify_amortized(n=1 << 16, growth=2):
    a = DynamicArray(growth=growth)
    for i in range(n):
        a.append(i)
    # 均摊 = 总拷贝次数 / n;成倍扩容时应接近常数(< growth/(growth-1))
    print(
        f"growth={growth}  n={n}  总拷贝={a.total_copies}  "
        f"均摊={a.total_copies / n:.4f}  最终容量={a._cap}"
    )


if __name__ == "__main__":
    verify_amortized(growth=2)     # 实测均摊 ≈ 1.0 个元素 -> O(1)
    verify_amortized(growth=3)     # 实测均摊 ≈ 0.6 个元素 -> O(1)
    # 实测结论:growth=2 时均摊约 1.0 次拷贝/append,growth=3 时约 0.6 次,
    # 增长因子越大均摊越低,但都是常数 —— 这就是 O(1) 的含义。
    #
    # 反面教材:growth=1(每次只把容量加 1 倍,等于不扩)会立刻越界崩溃,
    # 因为容量乘以 1 还是原容量。若改成"容量 +1",则每次都全量拷贝,
    # 总代价 1+2+...+n = O(n^2),均摊 O(n)。
    # 结论:扩容因子必须 > 1,这是均摊 O(1) 的必要条件。
例子 2:并查集的路径压缩

并查集(DSU)只有两个操作:find 与 union。

路径压缩:find(x) 时把路径上所有节点直接挂到根上。单次 find 最坏可以是 (一条长链,第一次查询),但均摊结果非常漂亮:

其中 是反阿克曼函数(Inverse Ackermann Function),它的增长速度慢到荒谬:

3
(宇宙原子数)4
5

在一切物理上可写出的 范围内,,所以并查集可以视为 均摊。

这里用势能法(Potential Method)更自然:定义势能 为「所有节点到根的距离之和」,路径压缩会一次性大幅降低 ,从而「预付」了后续操作的代价。这里只做定性说明,严格的势能证明需要引入秩(rank)与 的分级,可参考《算法导论》第 21 章。

"""并查集:路径压缩 + 按秩合并,实测单次操作平均代价趋于常数。"""
import time


class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.find_calls = 0
        self.total_steps = 0     # 累计 while 循环次数

    def find(self, x):
        self.find_calls += 1
        steps = 0
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
            steps += 1
        # 路径压缩:把路径上每个点直接指向根
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root
            x = nxt
            steps += 1
        self.total_steps += steps
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True


def benchmark(n=200_000):
    dsu = DSU(n)
    # 先制造一条长链(最坏结构):1 挂到 0,2 挂到 1,...
    for i in range(1, n):
        dsu.parent[i] = i - 1
    start = time.perf_counter()
    for i in range(n):
        dsu.find(i)          # 第一次 find(n-1) 代价 O(n),之后全部被压缩成 O(1)
    elapsed = time.perf_counter() - start
    print(
        f"n={n}  find 次数={dsu.find_calls}  平均步数={dsu.total_steps / dsu.find_calls:.3f}  "
        f"耗时={elapsed:.3f}s"
    )
    # 平均步数在 1~2 之间 -> 均摊接近 O(1),尽管第一次调用是 O(n)


if __name__ == "__main__":
    benchmark()
均摊分析的三种方法
方法思路适合场景
聚合法(Aggregate)算出 次操作的总代价 ,均摊 = 动态数组扩容(本文用的方法)
记账法(Accounting)给便宜操作多记一点「信用」,供昂贵操作抵扣栈操作、二进制计数器
势能法(Potential)定义势函数 ,均摊代价 = 实际代价 + 并查集、伸展树(Splay Tree)

四、递归算法分析

递归算法的代价由递推式(Recurrence)描述。三种求解方法:

方法 1:递归树法(Recursion Tree)

把递归展开成一棵树,每层的代价相加,再乘以层数。

例:归并排序

层子问题个数每个规模每层总代价
01
12
24

树高:,共 层。

总代价 。

方法 2:代入法(Substitution / 归纳法)

步骤:① 猜答案;② 用数学归纳法证明;③ 解出常数。

例:证明 满足 。

猜测:(对某个 )。

归纳:假设对所有 成立,则

只要 ,就有 ,于是 。证毕。

代入法的小技巧

减去低阶项时常常会「差一点」,可以适当放大猜测,例如猜 ,

这样归纳时有更大的腾挪空间。这是《算法导论》4.3 节推荐的技巧。

方法 3:主定理(Master Theorem)

对形如

的递推式,令临界指数 ,比较 与 :

情况条件结论直觉
情况 1,叶子占主导:递归部分太贵,底层工作量压倒合并
情况 2,每层一样贵: 层各贡献相同
情况 3 且 ,根占主导:合并太贵,顶层工作量压倒

主定理的三个「不适用」盲区

① 与 只差一个 因子之外的东西,如 ,落在情况 2 与情况 3 之间的缝隙;

② 子问题规模不整齐,如 ;

③ 不是常数,如 。

遇到这些要用递归树或代入法。

主定理例题 1:归并排序

,,,所以 。

,属于情况 2():

主定理例题 2:二分查找

,,,所以 。

,属于情况 2():

主定理例题 3:Strassen 矩阵乘法

,,。

,而 (取 ),属于情况 1:

比朴素矩阵乘法的 快,这是 1969 年 Strassen 的著名突破。

主定理例题 4(情况 3):一个合并极贵的例子

,,,(),

且正则条件满足(,取 ),属于情况 3:

主定理例题 5(易错): 属于哪种情况?

,。,(),

属于情况 3:

直觉:每次递归规模减半,但当前层的代价 支配了一切,几何级数 。

主定理速查实战
递推式情况结果
2212
1202
4221
722.8071
2213
8231
13/202
321.5851
"""用递归树/迭代展开法实际求解递推式,并与主定理结论对照。

只适合"子问题规模整齐"的递推式;这里用数值迭代验证增长量级。
"""
import math


def solve_recurrence(a, b, f_desc, n, memo=None):
    """数值求解 T(n) = a*T(n/b) + f(n),用于验证增长量级。

    f_desc: 'n' | 'n2' | '1' | 'nlogn'
    为避免指数爆炸,只对较小 n 调用;用记忆化减少重复。
    """
    if n <= 1:
        return 1.0
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]

    if f_desc == "n":
        f = n
    elif f_desc == "n2":
        f = n * n
    elif f_desc == "1":
        f = 1
    elif f_desc == "nlogn":
        f = n * math.log2(n)
    else:
        raise ValueError(f_desc)

    sub = int(n // b)
    res = a * solve_recurrence(a, b, f_desc, sub, memo) + f
    memo[n] = res
    return res


def master(a, b, f_power, f_log_power=0):
    """按主定理给出结论。f(n) = Theta(n^f_power * log^f_log_power n)。"""
    crit = math.log(a, b)
    if f_power < crit - 1e-9:
        return f"Theta(n^{crit:.3f})  [情况1]"
    if abs(f_power - crit) < 1e-9:
        return f"Theta(n^{crit:.3f} * log^{f_log_power + 1} n)  [情况2]"
    return f"Theta(n^{f_power})  [情况3]"


if __name__ == "__main__":
    cases = [
        (2, 2, "n", 1.0, 0, "归并排序"),
        (1, 2, "1", 0.0, 0, "二分查找"),
        (4, 2, "n", 1.0, 0, "a=4,b=2"),
        (7, 2, "n2", 2.0, 0, "Strassen"),
        (2, 2, "n2", 2.0, 0, "合并极贵"),
    ]
    for a, b, fdesc, fp, flp, name in cases:
        print(f"{name:12s} 主定理: {master(a, b, fp, flp)}")
        # 数值验证:n 翻倍时结果增长的倍数符合预期量级
        for n in (1024, 2048, 4096):
            print(f"    n={n:5d}  T(n)={solve_recurrence(a, b, fdesc, n):16.1f}")

五、空间复杂度与递归栈

空间复杂度统计算法运行过程中额外占用的内存,不含输入本身,记作「原地 / 非原地」。

来源说明例子
辅助数组显式申请的数组归并排序的合并数组
递归栈每层递归保存参数、局部变量、返回地址快排最坏 ,平均
哈希表用于去重或缓存两数之和
结果存储题目要求输出的一般不计入—
递归栈深度的重要性

递归的空间复杂度 = 最大递归深度,而不是递归调用总次数。

算法递归深度栈空间
二分查找
归并排序
快速排序(平均)
快速排序(最坏)
朴素 DFS(链状图)

Python 递归的真实限制

CPython 默认递归限制是 1000 层(sys.getrecursionlimit())。超过就抛

RecursionError: maximum recursion depth exceeded。

即使调大 setrecursionlimit,C 栈也可能先溢出导致段错误(Segmentation fault),进程直接崩溃、无法捕获。

处理 的深递归(如树的 DFS、图的 DFS)时,正确做法是:

① 改写为显式栈的迭代版本;② 或用 threading.stack_size() 起一个大栈线程。

"""空间复杂度与递归深度的实测。"""
import sys
import threading


def depth_recursive(n):
    """最简单的递归:深度 = n,测出实际能跑到多深。"""
    if n == 0:
        return 0
    return 1 + depth_recursive(n - 1)


def measure_python_recursion_limit():
    """二分搜索最大可递归深度,观察 CPython 的实际行为。"""
    lo, hi = 1, 200_000
    while lo < hi:
        mid = (lo + hi + 1) // 2
        try:
            sys.setrecursionlimit(mid + 200)
            depth_recursive(mid)
            lo = mid          # 没炸,说明还能更深
        except RecursionError:
            hi = mid - 1
    return lo


def run_in_big_stack(n):
    """在大栈线程里跑深递归,绕开 CPython 的默认线程栈限制。"""
    result = {}

    def worker():
        sys.setrecursionlimit(n + 1000)
        result["depth"] = depth_recursive(n)

    # 默认线程栈往往只有 1~8 MB;32 MB 可以支撑更深的递归
    threading.stack_size(64 * 1024 * 1024)
    t = threading.Thread(target=worker)
    t.start()
    t.join()
    return result.get("depth")


if __name__ == "__main__":
    print("默认递归上限:", sys.getrecursionlimit())     # 通常是 1000
    print("不改设置直接跑 5000 深:")
    try:
        depth_recursive(5000)
    except RecursionError as e:
        print("  失败 ->", e)                          # 印证上面的结论

    # 注意:调大限制只解除了 Python 的"计数器",真实的 C 栈上限由解释器的
    # 栈空间决定。CPython 3.11+ 对纯 Python 递归做了优化,实测可以跑到
    # 数十万层;但在更深或涉及 C 层调用的递归中,仍可能直接段错误。
    print("实际可达到的深度约:", measure_python_recursion_limit())
    print("大栈线程里跑 100000 深:", run_in_big_stack(100_000))
    # 工程结论:不要依赖"调大 setrecursionlimit"来救深递归,
    # 稳健做法是改写成显式栈的迭代版本(见 [[数据结构-图]] 的迭代 DFS)。

空间换时间的常见取舍

| 需求 | 选择 |

|---|---|

| 内存紧张(嵌入式) | 原地排序(堆排序 空间) |

| 要求稳定 | 归并排序( 空间) |

| 需要去重 / 计数 | 哈希表( 空间换 查询) |

| 缓存中间结果 | 记忆化搜索 / DP 表( 或 ) |

六、常见算法复杂度速查表

算法最好平均最坏空间备注
数组随机访问—
链表按下标访问只能在头部
哈希表查找最坏来自大量冲突
平衡 BST 查找红黑树、AVL
二分查找必须有序
冒泡排序稳定
插入排序稳定,小数组最快
选择排序交换次数最少
希尔排序取决于增量不稳定
归并排序稳定
快速排序不稳定,实际最快
堆排序不稳定,空间最优
计数排序要求整数值域小
基数排序稳定子排序才成立
桶排序依赖均匀分布
BFS / DFS邻接表
Dijkstra(堆优化)—无负权
Bellman-Ford—可判负环
Floyd-Warshall—多源
Kruskal—稀疏图
Prim(堆优化)—稠密图
并查集(单次)均摊近常数
0-1 背包(DP)—伪多项式

完整排序算法对比见 算法-排序

上图只给了排序的复杂度骨架。稳定性、原地性、递推式与代码实现见专门笔记。

七、P、NP 与 NP 完全问题

问题分类
类定义直观例子
P存在多项式时间算法求解的判定问题好解排序、最短路、二分查找、判断图是否连通
NP存在多项式时间算法验证一个给定解的问题好验证数独、哈密顿路径、布尔可满足性
NP 难(NP-hard)所有 NP 问题都能多项式归约到它(但自己不一定在 NP 中)至少一样难旅行商问题的优化版、停机问题
NP 完全(NP-complete)既在 NP 中,又是 NP 难难中之难SAT、3-SAT、哈密顿回路、旅行商判定版、背包判定版

关系:,而 NP 完全问题是 NP 中「最难」的那一批。

为什么说这是开放问题

核心问题: 吗?

  • 已知:如果任何一个 NP 完全问题存在多项式算法,那么所有 NP 问题都有多项式算法()
  • 已知: 都不被证明——至今没有人能证明 ,也没人能证明
  • 这是克雷数学研究所七个千禧年大奖难题之一,悬赏 100 万美元

为什么它这么重要

如果 ,那么:蛋白质折叠、最优物流调度、密码分析(RSA 会被多项式破解)、

自动定理证明、芯片布线优化——所有这些都会变得「可高效求解」。

反过来,如果 (学界普遍相信如此),那么这些问题只能求近似解或启发式解。

现代密码学的安全性就建立在「 且某些问题确实难解」这个(未被证明的)假设之上。

面对 NP 完全问题的工程策略
策略说明例子
缩小规模用状态压缩把 压到可行范围()状压 DP 解 TSP,
近似算法放弃最优,保证近似比TSP 的 Christofides 算法,近似比 1.5
启发式 / 元启发式无最优保证,实践中很好模拟退火、遗传算法、蚁群算法
分支限界用上界剪枝,平均情况很快整数规划求解器(Gurobi、CPLEX)
参数化算法复杂度写成 , 为某个小参数顶点覆盖的 算法
约束求解器交给 SAT / SMT 求解器Z3、MiniSat
"""哈密顿路径(NP 完全)的状压 DP 解法,演示"缩小规模"策略。

状态: dp[mask][v] = 从起点出发、已访问集合为 mask、当前停在 v 是否可行
转移: dp[mask | 1<<u][u] |= dp[mask][v]  若存在边 v->u
复杂度: O(2^n * n^2) —— n=20 时约 4 亿,勉强可跑;n=25 就完全不行了
"""


def hamiltonian_path(n, adj):
    """adj[u] 是 u 的出边集合。返回是否存在哈密顿路径。"""
    size = 1 << n
    # dp[mask] 用位图表示"以 v 结尾是否可行"
    dp = [0] * size
    for v in range(n):
        dp[1 << v] = 1 << v        # 单点路径:以 v 结尾的可行集合是 {v}
    for mask in range(size):
        if dp[mask] == 0:
            continue
        ends = dp[mask]
        v = 0
        while ends:
            if ends & 1:
                for u in adj[v]:
                    if not (mask >> u) & 1:
                        dp[mask | (1 << u)] |= 1 << u
            ends >>= 1
            v += 1
    full = size - 1
    return dp[full] != 0


if __name__ == "__main__":
    # 5 个点的完全图一定有哈密顿路径
    n = 5
    adj = [[u for u in range(n) if u != v] for v in range(n)]
    print("完全图 K5 有哈密顿路径:", hamiltonian_path(n, adj))    # True

    # 去掉一些边后可能没有
    n2 = 4
    adj2 = [[1], [2], [3], []]      # 一条链 0->1->2->3
    print("链 0->1->2->3 有哈密顿路径:", hamiltonian_path(n2, adj2))  # True

    adj3 = [[1], [0], [3], [2]]     # 两个不相连的二元环
    print("两个分离二元环:", hamiltonian_path(4, adj3))            # False

八、工程中如何估算性能

四步估算法

第 1 步:确定 的真实量级。 是每天 1000 条还是每秒 100 万条?差 6 个数量级,方案完全不同。

第 2 步:写出复杂度,算出操作次数。

第 3 步:选「每次操作」的单价。 经验值:

操作大致耗时说明
CPU 一级缓存访问1 ns4 个时钟周期
CPU 主存随机访问100 ns缓存未命中惩罚
顺序扫描 1 字节~0.1 ns内存带宽约 10 GB/s
Python 一次循环迭代30~100 ns比 C 慢 30~50 倍
Python 字典查询40~80 nsC 实现的哈希查找
磁盘 SSD 随机读100 μs比内存慢 1000 倍
同机房网络往返0.5 ms—
跨大西洋网络往返150 ms光速限制

第 4 步:与预算比较。 Web 接口通常要求 P99 < 200 ms;批量任务可以放宽到分钟级。

估算实例:给 1000 万用户发推送
"""估算练习:把"理论复杂度"翻译成"能不能在上线前跑完"。"""

# 场景:10^7 个用户,需要按 (城市, 活跃度) 排序后分批推送
N = 10_000_000
COST_PER_OP = 50e-9      # 保守估计:Python 每次基本操作 50 ns
BUDGET_SECONDS = 300     # 批处理预算:5 分钟


def estimate(name, ops, cost=COST_PER_OP, budget=BUDGET_SECONDS):
    seconds = ops * cost
    ok = "✅ 通过" if seconds <= budget else "❌ 超预算"
    print(
        f"{name:28s} 操作数={ops:.3e}  预估耗时={seconds:10.2f}s  {ok}"
    )
    return seconds


if __name__ == "__main__":
    import math

    print(f"数据规模 n = {N:,},单价 {COST_PER_OP*1e9:.0f} ns/操作,预算 {BUDGET_SECONDS}s\n")

    estimate("O(n) 一次遍历", N)
    estimate("O(n log n) 排序", N * math.log2(N))
    estimate("O(n^1.5) 分块", N ** 1.5)
    estimate("O(n^2) 两两比较", N * N)

    # 结论:n=10^7 时,O(n) 约 0.5 s、O(n log n) 约 12 s 都可以接受,
    # O(n^2) 是 5.8 天,直接淘汰。这就是"先算复杂度再写代码"的价值。

更精确的估算:用 timeit 实测单价

上面的 50 ns 是保守估计。想知道自己机器上真实单价,用标准库 timeit:

```python

import timeit

t = timeit.timeit("for i in range(1000): pass", number=1000)

print(f"每 1000 次循环耗时 {t/1000*1e6:.2f} 微秒")

```

官方文档:https://docs.python.org/3/library/timeit.html

什么时候不该操心复杂度

常数与可读性的权衡

复杂度分析的前提是「 足够大」。如果 永远不超过 50(比如解析一个配置文件的字段),

写 的双重循环远比写一个 的复杂算法更好维护。

优化的第一原则是「先测量,再优化」——不要凭直觉给非热点代码做复杂度优化。

怎么用

快速判断一段代码的复杂度

"""通过几个典型代码片段,练习"数循环"的复杂度判断法。"""


def o1(arr):
    return arr[0] if arr else None           # 单条语句 -> O(1)


def on(arr):
    total = 0
    for x in arr:                            # 循环 n 次
        total += x
    return total                             # -> O(n)


def on2(arr):
    n = len(arr)
    cnt = 0
    for i in range(n):                       # 外层 n 次
        for j in range(n):                   # 内层 n 次
            cnt += 1
    return cnt                               # -> O(n^2)


def onlogn(arr):
    n = len(arr)
    cnt = 0
    for i in range(n):                       # 外层 n 次
        j = n
        while j > 1:                         # 内层 log n 次
            j //= 2
            cnt += 1
    return cnt                               # -> O(n log n)


def on_inner_triangle(arr):
    n = len(arr)
    cnt = 0
    for i in range(n):
        for j in range(i + 1, n):            # 内层平均 n/2 次
            cnt += 1
    return cnt                               # n(n-1)/2 -> 仍是 O(n^2)


def o_log_n_sqrt_n(n):
    cnt = 0
    i = 1
    while i * i <= n:                        # sqrt(n) 次
        j = n
        while j > 1:
            j //= 2                          # log n 次
            cnt += 1
        i += 1
    return cnt                               # -> O(sqrt(n) log n)


if __name__ == "__main__":
    print(o1([1, 2, 3]))
    print(on([1, 2, 3]))
    print(on2([1, 2, 3]))
    print(onlogn([1, 2, 3]))
    print(on_inner_triangle([1, 2, 3, 4]))
    print(o_log_n_sqrt_n(1000))

数循环的三条规则

规则情形结论
加法规则两段顺序代码,复杂度 与 总复杂度
乘法规则循环嵌套 / 递归调用复杂度相乘
只看最高阶

递推式的实用判定流程

遇到 T(n) = a*T(n/b) + f(n)?
├── 子问题规模整齐(都是 n/b)?
│   ├── 是 → 算 c* = log_b(a)
│   │        ├── f(n) 远小于 n^c*  → Theta(n^c*)      (情况1)
│   │        ├── f(n) 同量级       → Theta(n^c* log n) (情况2)
│   │        └── f(n) 远大于 n^c*  → Theta(f(n))       (情况3)
│   └── 否(如 T(n/3)+T(2n/3))→ 用递归树逐层求和
└── 不是标准形式(如 T(sqrt n))→ 换元 或 递归树

注意事项与常见坑

坑 1:把 当精确值比较常数

说「 比 慢一倍」是错的——渐进记号里 。

常数差异要用实测(timeit)或具体操作计数来比较,不能用大 比。

坑 2:忽略 Python 内建函数的真实复杂度

| 写法 | 真实复杂度 | 常见误解 |

|---|---|---|

| x in list | | 以为是 |

| list.insert(0, x) | | 以为是 (要整体后移) |

| list.pop(0) | | 应改用 collections.deque.popleft() |

| list.append(x) | 均摊 | 正确 |

| x in set / x in dict | 平均 ,最坏 | 忽略最坏情况 |

| "a" in "abc" | | 忽略子串匹配代价 |

| sorted(list) | | 正确 |

| lst[a:b] 切片 | | 以为是 |

坑 3:在循环里做字符串拼接

```python

# 慢:每轮都新建字符串并复制全部已有内容 -> O(n^2)

s = ""

for x in data:

s += x

# 快:append 均摊 O(1),最后 join 一次 O(n) -> O(n)

parts = []

for x in data:

parts.append(x)

s = "".join(parts)

```

后者是 CPython 官方推荐写法(''.join() 会先算总长度,只分配一次内存)。

坑 4:混淆「均摊」与「最坏」

list.append 均摊 ,但单次可能 。

对延迟敏感的实时系统(如游戏渲染循环、高频交易),均摊 不等于每一帧都够快——

必须关注单次最坏延迟,必要时用预分配容量来消除扩容抖动。

坑 5:忘了空间复杂度里的递归栈

「我的快排是原地排序,空间 」——错。递归栈平均要 ,最坏 。

真正 空间的排序是堆排序。

坑 6:主定理正则条件被忽略

情况 3 除了要求 ,还要求正则条件 ()。

绝大多数常见的 (多项式、)都满足,但构造性的反例存在。

严格证明时应验证这一步。

坑 7:把「平均情况」当成「所有情况」

哈希表查询平均 ,但如果攻击者能构造大量哈希冲突的键(哈希碰撞攻击),

就能让每次查询退化到 ,把服务打挂。

防御手段:随机化哈希种子(Python 从 3.3 起默认开启 PYTHONHASHSEED 随机化)、用平衡树替代链表。

坑 8:误判 是「接近线性」就无所谓

时 ,是 的 20 倍。

对 1 秒预算的服务来说,这 20 倍可能是决定性差异。任何复杂度都要代入具体 算一遍。

坑 9:伪多项式不是多项式

0-1 背包的 看起来像多项式,但 是数值大小而非输入位长。

若 ,输入只需 100 位,而算法要 步。

所以背包问题是 NP 难的——这类复杂度叫伪多项式(Pseudo-polynomial)。

练习题

题 1(基础)判断复杂度

判断下列每段代码的时间复杂度:

# (a)
for i in range(n):
    for j in range(n):
        for k in range(n):
            pass

# (b)
i = n
while i > 1:
    i //= 3

# (c)
for i in range(n):
    j = 1
    while j < n:
        j *= 2

# (d)
for i in range(n):
    for j in range(i):
        pass

<details>

<summary>参考答案</summary>

  • (a) :三层各 次的循环相乘
  • (b) :每次除以 3,需要 次
  • (c) :外层 次,内层 从 1 倍增到 需 次
  • (d) :内层次数 ,最高阶是

</details>

题 2(基础)写出递推式

写出「在 个元素中同时找出最大值和最小值,采用分治:把数组分成两半,分别求最值再合并」的递推式并求解。

<details>

<summary>参考答案</summary>

,,,。(),属于情况 1。

结论:分治法求最值仍是线性时间,但比较次数从朴素的 降到约 。

</details>

题 3(中等)用主定理求解下面三个递推式

(1)

(2)

(3)

完整分步解答:


(1)

第 1 步:识别参数。 (子问题个数),(规模缩小倍数),。

第 2 步:计算临界指数。

第 3 步:比较 与 。 ,而 ,所以

第 4 步:判定为情况 1(叶子代价占主导),结论:

第 5 步:直觉验证(递归树)。 第 层有 个子问题,每个规模 ,该层代价 ,随层数递增,所以最后一层最大。

(用到 。)


(2)

第 1 步: ,,。

第 2 步:

第 3 步: ,恰好同量级。

第 4 步:判定为情况 2():

第 5 步:直觉验证。 每层代价都是 ,共 层,总计 。✓


(3)

第 1 步: ,,。

第 2 步:

第 3 步: ,恰好同量级。

第 4 步:判定为情况 2():

第 5 步:直觉验证。 每层代价 ,恒定;层数 ,总计 。✓

</details>

题 4(中等)均摊分析:二进制计数器

一个 位二进制计数器从 0 开始,反复加 1,共加 次。第 位每次翻转的代价是 1。用聚合法证明均摊每次操作代价为 。

完整分步解答:

第 1 步:观察翻转规律。 从 0 数到 :

加 1 次数二进制翻转的位
10001第 0 位
20010第 0、1 位
30011第 0 位
40100第 0、1、2 位
50101第 0 位
60110第 0、1 位
70111第 0 位
81000第 0、1、2、3 位

第 2 步:统计每一位翻了多少次。

位翻转频率 次操作的总翻转次数
第 0 位(最低位)每次都翻
第 1 位每 2 次翻一次
第 2 位每 4 次翻一次
第 位每 次翻一次

第 3 步:求和。

(几何级数 收敛,所以无论 多大,总和都是 。)

第 4 步:均摊。

结论:尽管单次操作最坏要翻转 位,均摊到每次仍是 。✓

</details>

题 5(进阶)为什么快排的最坏情况是 ?

写出快排在「每次划分极不均匀」时的递推式,用代入法求解,并说明随机化为什么能避免它。

<details>

<summary>参考答案</summary>

递推式(每次划分只减少 1 个元素):

展开:

何时发生:数组已经有序(或逆序),且固定取首元素(或末元素)作基准。每次划分只能分出「0 个元素」和「 个元素」。

为什么随机化有效:随机选基准后,任何固定输入都无法保证每次都划分不均——划分结果成为随机变量。可以证明(《算法导论》7.4.2),随机化快排的期望复杂度是 ,且退化到 的概率随 增大指数级下降。

工程实现:除了随机化,还用三数取中(median-of-three)(取首、中、尾三者的中位数作基准)和小区间切换插入排序( 时插入排序更快)。

详见 算法-排序 的快速排序一节。

</details>

题 6(进阶)用估算判断方案可行性

某服务每天要给 条记录做「两两相似度计算」。相似度函数耗时 2 μs。方案 A 是暴力两两比较,方案 B 是用局部敏感哈希(LSH)降到 次函数调用。判断方案 A 是否可行(预算 1 小时)。

<details>

<summary>参考答案</summary>

方案 A:两两比较共

耗时:

远超 1 小时预算,方案 A 不可行。

方案 B:

10 秒,完全可行。(再叠加一次 排序, 次操作,仍可接受。)

结论: 到百万级时, 一律出局,必须降复杂度。

</details>

常见问题 FAQ

Q1:、、 到底哪个"更好"?能给出排序吗?

从小到大的完整顺序是:

判断方法:取极限 。若为 0 则 更小,为 则 更大。

注意 与 、 只是常数倍差异,都写作 。

Q2:为什么算法分析里 的底数不重要?

换底公式:,其中 是常数。

渐进记号忽略常数因子,所以 ,统一写 。

例外:指数中的底数不能忽略——,因为 不是常数。

Q3:主定理能覆盖所有递推式吗?

不能。它只处理 这一种标准形式。三类常见例外:

① 子问题规模不等(,答案是 ,用递归树);

② 规模不是除法而是减法(,直接展开得 );

③ 落在情况之间(如 ,答案是 ,用递归树)。

后者的递归树每层代价 ,求和后得 。

Q4:实际项目里什么时候需要做复杂度分析?

四个时机:① 写代码前选方案(决定用哈希表还是嵌套循环);② Code Review 时识别隐患(发现循环里嵌套了 in list);③ 性能问题定位(用 profiler 找到热点,再判断是复杂度问题还是常数问题);④ 容量规划(预估数据量增长 10 倍后是否还能跑)。

日常写 100 行的脚本、处理 1000 条数据时,不需要刻意套用主定理——可读性优先。

Q5:为什么同样的复杂度,Python 比 C 慢几十倍,复杂度分析还有意义?

因为复杂度描述的是增长趋势,趋势与常数无关。 从 涨到 时, 方案无论用 C 还是汇编都会慢 100 倍,而 只慢约 11 倍。

常数决定「起点高低」,复杂度决定「斜率」。数据量足够大时,斜率是决定性的。

但反过来说: 不大时,常数才是关键——这也是为什么小数组用插入排序比快排快。

相关笔记

  • 算法-排序:复杂度分析最典型的应用战场,十种排序的对比与递推式
  • 数据结构-图:、 等图算法复杂度结论的来源
  • 算法-查找与分治:二分查找 与分治递推式的实战
  • 算法-动态规划与贪心:伪多项式复杂度与状态空间分析
  • 数据结构-树与堆:平衡树 的由来与堆操作复杂度
  • 00-索引:全库笔记导航
  • 学习路线图:按阶段的学习顺序建议

参考来源

  • OI Wiki 复杂度:https://oi-wiki.org/basic/complexity/
  • OI Wiki 主定理:https://oi-wiki.org/basic/complexity/#主定理
  • MIT OCW 6.006 Introduction to Algorithms(含均摊分析与主定理):https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
  • Python 官方文档 timeit:https://docs.python.org/3/library/timeit.html
  • Python 官方文档 sys.setrecursionlimit:https://docs.python.org/3/library/sys.html#sys.setrecursionlimit
  • Python 官方文档 threading.stack_size:https://docs.python.org/3/library/threading.html#threading.stack_size
  • CPython 源码 list_resize(动态数组扩容策略):https://github.com/python/cpython/blob/main/Objects/listobject.c
  • VisuAlgo 算法可视化:https://visualgo.net/en
  • 克雷数学研究所千禧年大奖难题 P vs NP:https://www.claymath.org/millennium-problems/p-vs-np-problem