核心问题 ：哪些问题可以被有效计算？哪些问题本质上难以求解？这既是数学的极限探索，也是计算机科学的理论根基。
算法与复杂性理论（Computational Complexity Theory）研究计算问题所需的资源（时间、空间等）与问题规模之间的关系。它不仅回答"能否计算"，更回答"需要多少资源才能计算"。从图灵机的抽象模型到 P vs NP 的世纪难题，这一理论深刻影响着密码学、优化、人工智能等领域的实践，也是每个程序员理解"什么可行、什么不可行"的理论基石。
图灵机（Turing Machine, TM）由艾伦·图灵于1936年在其开创性论文《论可计算数及其在判定问题上的应用》中提出，是计算理论中最基础的抽象模型。尽管构造简单——只有一条无限纸带和一个读写头——图灵机足以模拟任何现代计算机的计算过程。这就是丘奇-图灵论题 （Church-Turing Thesis）的核心主张：一切"合理"的计算模型在计算能力上等价于图灵机。
基本构成 ：
无限长的纸带 （tape）：被划分为连续单元，每个单元存储一个来自有限符号集 Γ Γ 读写头 （head）：可沿纸带左右移动，读取和写入符号状态寄存器 ：存储有限个内部状态 Q Q q 0 q 0 q accept q accept q reject q reject 转移函数 ：δ : Q × Γ → Q × Γ × { L , R } δ : Q × Γ → Q × Γ × { L , R }
工作过程 ：机器根据当前状态 q ∈ Q q ∈ Q γ ∈ Γ γ ∈ Γ δ ( q , γ ) = ( q ′ , γ ′ , d ) δ ( q , γ ) = ( q ′ , γ ′ , d ) γ ′ γ ′ d ∈ { L , R } d ∈ { L , R } q ′ q ′
形式化定义 ：一台图灵机可表示为一个7元组 M = ( Q , Σ , Γ , δ , q 0 , q accept , q reject ) M = ( Q , Σ , Γ , δ , q 0 , q accept , q reject ) Σ ⊆ Γ Σ ⊆ Γ B ∈ Γ ∖ Σ B ∈ Γ ∖ Σ
重要变体 ：
确定性图灵机（DTM） ：每个状态-符号对只有一种可能的转移，计算路径唯一非确定性图灵机（NTM） ：允许一个状态-符号对有多个转移选项，只要其中一个分支能接受即视为接受——这并非物理可实现，而是重要的理论工具多带图灵机 ：拥有多条纸带，计算能力等价于单带图灵机，但效率可能呈多项式倍数提升通用图灵机（UTM） ：可以读取任意图灵机的描述并在其上运行——现代计算机的理论原型，也是存储程序概念（von Neumann 架构）的先驱
一切"合理"的计算模型在计算能力上都是等价的。
这一论题并非数学定理，而是一个被广泛接受的实证结论。所有已知的计算模型——λ λ
这一统一性暗示计算是一个深刻的物理和数学概念，而非特定技术的产物。
可判定问题（Decidable Problem） ：存在一个算法能在有限步内判定任意输入的答案。例如：
判断一个整数是否为素数（AKS 素性测试，2002年）
判断一个字符串是否为回文
判断一个有限图是否连通
判断一个命题逻辑公式是否可满足（仅对有限变元）
不可判定问题（Undecidable Problem） ：不存在算法能在有限步内对所有输入给出正确答案。最著名的例子是停机问题（Halting Problem） ：不存在一个通用算法能判断任意程序是否会在有限步内终止。
图灵证明停机问题不可判定的核心思想是对角线法 （与康托尔证明实数不可数、哥德尔证明不完备定理的方法一脉相承）：
假设存在算法 H ( P , I ) H ( P , I ) P P I I
构造一个新程序 C ( P ) C ( P ) H ( P , P ) H ( P , P )
当将 C C C C
其他不可判定问题 ：
希尔伯特第十问题 ：整数系数多项式方程是否存在整数解（不可判定，Matijasevich 定理）字问题（Word Problem for Groups） ：给定群的生成元和关系，判断两个词是否表示同一个群元素Post 对应问题 ：多米诺骨牌的匹配问题
这些结果划定了计算的"理论边界"——有些问题永远不能被算法解决，无论计算能力多强。
算法的时间复杂度通常用大 O 符号（Big O O n n
形式定义 ：
O ( g ( n ) ) = { f ( n ) ∣ ∃ c > 0 , n 0 > 0 , ∀ n ≥ n 0 : 0 ≤ f ( n ) ≤ c ⋅ g ( n ) } O ( g ( n ) ) = { f ( n ) ∣ ∃ c > 0 , n 0 > 0 , ∀ n ≥ n 0 : 0 ≤ f ( n ) ≤ c ⋅ g ( n ) }
直观来说，f ( n ) = O ( g ( n ) ) f ( n ) = O ( g ( n ) ) c c f ( n ) ≤ c ⋅ g ( n ) f ( n ) ≤ c ⋅ g ( n ) n n
其他渐进符号 ：
大 Ω Ω （渐近下界）：f ( n ) = Ω ( g ( n ) ) f ( n ) = Ω ( g ( n ) ) c > 0 c > 0 n 0 n 0 f ( n ) ≥ c ⋅ g ( n ) f ( n ) ≥ c ⋅ g ( n ) n ≥ n 0 n ≥ n 0 大 Θ Θ （紧渐近界）：f ( n ) = Θ ( g ( n ) ) f ( n ) = Θ ( g ( n ) ) f ( n ) = O ( g ( n ) ) f ( n ) = O ( g ( n ) ) f ( n ) = Ω ( g ( n ) ) f ( n ) = Ω ( g ( n ) ) 小 o o （严格上界）：f ( n ) = o ( g ( n ) ) f ( n ) = o ( g ( n ) ) n → ∞ f ( n ) / g ( n ) = 0 lim n → ∞ f ( n ) / g ( n ) = 0
不同复杂度的算法在输入规模增大时的表现差异巨大：
复杂度
名称
典型问题
n = 1 0 6 n = 1 0 6
O ( 1 ) O ( 1 ) 常数时间
哈希表查找、数组下标访问
约1
O ( log n ) O ( log n ) 对数时间
二分查找、平衡树操作
约20
O ( n ) O ( n ) 线性时间
数组遍历、线性搜索
1 0 6 1 0 6
O ( n log n ) O ( n log n ) 线性对数时间
归并排序、快速排序（平均）
约 2 × 1 0 7 2 × 1 0 7
O ( n 2 ) O ( n 2 ) 平方时间
冒泡排序、朴素矩阵乘法
1 0 12 1 0 1 2
O ( n 3 ) O ( n 3 ) 立方时间
Floyd-Warshall 最短路径
1 0 18 1 0 1 8
O ( 2 n ) O ( 2 n ) 指数时间
旅行商问题（暴力搜索）
天文数字
O ( n ! ) O ( n ! ) 阶乘时间
排列枚举
荒谬
注意：2 1 0 6 2 1 0 6 1 0 80 1 0 8 0 1 0 6 log 1 0 6 ≈ 2 × 1 0 7 1 0 6 log 1 0 6 ≈ 2 × 1 0 7 算法选择决定了计算可行性的边界 。
对于分治算法的时间复杂度分析，**主定理（Master Theorem）**是一个强大的工具。考虑递归关系：
T ( n ) = a T ( n b ) + f ( n ) T ( n ) = a T ( b n ) + f ( n )
其中 a ≥ 1 a ≥ 1 b > 1 b > 1 f ( n ) f ( n )
若 f ( n ) = O ( n b a − ϵ ) f ( n ) = O ( n l o g b a − ϵ ) ϵ > 0 ϵ > 0 T ( n ) = Θ ( n b a ) T ( n ) = Θ ( n l o g b a )
若 f ( n ) = Θ ( n b a ) f ( n ) = Θ ( n l o g b a ) T ( n ) = Θ ( n b a log n ) T ( n ) = Θ ( n l o g b a log n )
若 f ( n ) = Ω ( n b a + ϵ ) f ( n ) = Ω ( n l o g b a + ϵ ) ϵ > 0 ϵ > 0 a f ( n / b ) ≤ c f ( n ) a f ( n / b ) ≤ c f ( n ) c < 1 c < 1 n n T ( n ) = Θ ( f ( n ) ) T ( n ) = Θ ( f ( n ) )
应用示例 ：
归并排序 ：T ( n ) = 2 T ( n / 2 ) + O ( n ) T ( n ) = 2 T ( n / 2 ) + O ( n ) b a = 2 2 = 1 log b a = log 2 2 = 1 f ( n ) = Θ ( n ) = Θ ( n b a ) f ( n ) = Θ ( n ) = Θ ( n l o g b a ) T ( n ) = Θ ( n log n ) T ( n ) = Θ ( n log n ) 二分查找 ：T ( n ) = T ( n / 2 ) + O ( 1 ) T ( n ) = T ( n / 2 ) + O ( 1 ) b a = 2 1 = 0 log b a = log 2 1 = 0 f ( n ) = O ( 1 ) = O ( n 0 ) f ( n ) = O ( 1 ) = O ( n 0 ) T ( n ) = Θ ( log n ) T ( n ) = Θ ( log n ) Strassen 矩阵乘法 ：T ( n ) = 7 T ( n / 2 ) + O ( n 2 ) T ( n ) = 7 T ( n / 2 ) + O ( n 2 ) b a = 2 7 ≈ 2.81 log b a = log 2 7 ≈ 2 . 8 1 f ( n ) = O ( n 2 ) = O ( n 2 7 − 0.81 ) f ( n ) = O ( n 2 ) = O ( n l o g 2 7 − 0 . 8 1 ) T ( n ) = Θ ( n 2 7 ) ≈ Θ ( n 2.81 ) T ( n ) = Θ ( n l o g 2 7 ) ≈ Θ ( n 2 . 8 1 )
摊还分析（Amortized Analysis）评估一个操作序列的平均时间成本，而非单次操作的最坏情况。三种常用方法：
聚合分析 ：计算 n n T ( n ) T ( n ) n n 记账法 ：为"便宜"操作预存信用，用于支付"昂贵"操作势能法 ：定义势能函数 Φ Φ Φ ( D i ) − Φ ( D i − 1 ) Φ ( D i ) − Φ ( D i − 1 )
经典例子 ：动态数组（如 C++ std::vector 或 Python list）的尾部插入。单次插入可能触发 O ( n ) O ( n ) n n O ( n ) O ( n ) O ( 1 ) O ( 1 ) 1 + 2 + 4 + ⋯ + 2 ⌊ 2 n ⌋ < 2 n 1 + 2 + 4 + ⋯ + 2 ⌊ l o g 2 n ⌋ < 2 n
空间复杂度衡量算法运行时占用的存储空间量，同样使用大 O O
输入空间 ：存储输入数据所需的空间辅助空间 ：算法运行过程中额外使用的空间（栈、堆等）输出空间 ：存储输出结果的空间
常数空间 O ( 1 ) O ( 1 ) ：原地算法，只使用有限个额外变量（如交换排序中的临时变量）对数空间 O ( log n ) O ( log n ) ：二分查找、某些递归算法的栈空间（如快速排序的平均递归深度为 O ( log n ) O ( log n ) 线性空间 O ( n ) O ( n ) ：存储输入数据的副本、哈希表、动态规划表多项式空间 O ( n k ) O ( n k ) ：全源最短路径的邻接矩阵、k k
许多问题允许在时间和空间之间做权衡：
记忆化（Memoization） ：用空间存储计算结果，避免重复计算，可将指数时间降为多项式时间。例如 Fibonacci 数列的朴素递归为 O ( 2 n ) O ( 2 n ) O ( n ) O ( n ) 预计算表 ：空间换时间的典型——查三角函数表、CRC 表、最近邻索引位压缩 ：用位操作替代数组，牺牲时间节省空间。如位图索引在数据库中的应用缓存与高速缓存 ：CPU 的 L1/L2/L3 缓存、网页 CDN、数据库缓存都是时间-空间权衡的体现
Hugo 的实践笔记 ：O ( n ⋅ m ) O ( n ⋅ m ) O ( k ) O ( k ) 在高并发系统中，空间换时间往往是正确的选择 。
复杂性类（Complexity Class）是所有可以在某种资源约束下求解的问题的集合。问题是决策问题（判定一个命题的真假），每个实例的答案是"是"或"否"。
复杂性类
资源约束
描述
P 多项式时间（DTM）
能用确定性图灵机在多项式时间内求解的问题
NP 多项式时间（NTM）
能用非确定性图灵机在多项式时间内求解，或解可在多项式时间内验证的问题
EXPTIME 指数时间（DTM）
O ( 2 p ( n ) ) O ( 2 p ( n ) )
PSPACE 多项式空间
能用多项式空间求解的问题
L 对数空间（DTM）
O ( log n ) O ( log n )
NL 对数空间（NTM）
非确定性对数空间可解的问题
BPP 随机多项式时间
概率算法能以高概率正确求解的问题
#P 计数问题
计数 NP 问题的解的个数
已知的复杂性类包含关系：
L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE
其中一些包含关系是严格的 ：
时间层级定理 （Time Hierarchy Theorem）：保证 P ⊊ ⊊ 空间层级定理 （Space Hierarchy Theorem）：保证 PSPACE ⊊ ⊊
但许多关键包含关系是否严格仍然是开放问题 ：
P 是否等于 NP？——世纪难题
NP 是否等于 co-NP
L 是否等于 NL
P 是否等于 PSPACE
归约（Reduction） 是复杂性理论的核心工具。若问题 A A B B A ≤ B A ≤ B B B A A A A B B B B
常用归约方式：
多项式时间归约 （Karp 归约，≤ p ≤ p 对数空间归约 ：更精细的归约，用于区分类中更细的层次（如 NL-完全性的证明）图灵归约 （≤ T ≤ T B B
完全性（Completeness） ：如果问题 X X C C C C X X X X C C C C
P （Polynomial time）：存在 c c A A n n A A O ( n c ) O ( n c ) 可在多项式时间内求解 。
NP （Nondeterministic Polynomial time）：对任何答案为"是"的实例，存在一个多项式大小的证据（certificate），可在多项式时间内验证其正确性。直观理解：解可在多项式时间内验证 。
核心问题 ：P 是否等于 NP？——即，如果一个问题可以在多项式时间内验证解，是否也意味着可以在多项式时间内找到解？
这是克雷数学研究所（Clay Mathematics Institute）公布的七个**千年难题（Millennium Prize Problems）**之一，悬赏一百万美元。大多数理论计算机科学家认为 P ≠ =
如果 P = NP（虽然普遍认为极不可能）：
许多当前认为困难的问题将变得可有效求解
公钥密码学将崩溃 ——RSA、椭圆曲线密码学等依赖"NP 问题难解"的基础将被打破数学定理证明可能自动化——给定任何数学命题，能在多项式时间内找到证明（如果证明存在）
人工智能的许多核心任务（计划、推理、学习）将变得可精确求解
优化、调度、物流等领域将发生革命性变化
如果 P ≠ =
某些重要问题在本质上难以求解
我们需要近似算法、启发式方法、随机化、参数化算法 等替代策略
密码学的安全性有了理论基础
我们理解了"创造性"（找到解）和"验证"（检查解）之间的本质区别
假设 P ≠ =
P ⊆ NP ⊆ NP NP ⊆ NP NP NP ⊆ ⋯ ⊆ PSPACE P ⊆ NP ⊆ NP NP ⊆ NP NP NP ⊆ ⋯ ⊆ PSPACE
其中 Σ 0 P = P Σ 0 P = P Σ 1 P = NP Σ 1 P = NP Σ k + 1 P = NP Σ k P Σ k + 1 P = NP Σ k P Σ k P Σ k P Π k P = co- Σ k P Π k P = co- Σ k P k k Σ k P = Π k P Σ k P = Π k P
NP 完全（NP-Complete, NPC）问题是 NP 类中最难的问题——它们满足：
属于 NP 类
所有 NP 问题都可以多项式时间归约到它
首个 NP 完全问题 ：Cook-Levin 定理 （1971年）证明了布尔可满足性问题（SAT）是 NP 完全的。其证明核心是：任意 NP 图灵机的计算过程可以被编码为一个布尔公式，使得公式可满足当且仅当图灵机接受输入。这开启了"NP 完全时代"。
著名的 NP 完全问题 （Karp 的 21 个 NP 完全问题，1972年）：
3-SAT ：合取范式中每个子句恰好包含三个文字的布尔可满足性问题顶点覆盖（Vertex Cover） ：找到覆盖所有边的最小顶点集团问题（Clique） ：找到图中最大的完全子图独立集（Independent Set） ：找到最大规模的成对不相邻的顶点集哈密顿回路（Hamiltonian Cycle） ：找到经过所有顶点恰好一次的回路旅行商问题（TSP） ：找到最短的哈密顿回路划分问题（Partition） ：将一组数分为两个和相等的子集背包问题（Knapsack） ：在重量限制下最大化价值图着色（Graph Coloring） ：用 k k 子集和（Subset Sum） ：是否存在和为目标的子集精确覆盖（Exact Cover） ：精确覆盖问题（Donald Knuth 的 Dancing Links 算法）
NP 难（NP-Hard） ：问题至少与 NP 中最难的问题一样难，但不一定属于 NP 类。NP 难问题可能：
不可判定（如停机问题）
不在 NP 中（如最优 TSP 的精确解，而非判定版本）
co-NP ：NP 的补类——"否"答案可在多项式时间内验证。例如，**合取范式的永真性（TAUTOLOGY）**属于 co-NP：要证明一个公式不是重言式，只需给出一个反例。
一个重要问题：**NP 是否等于 co-NP？**如果成立，则 NP 完全问题存在多项式大小的"无解证明"（而非仅有"有解证明"），这通常被认为不太可能。
虽然复杂性理论告诉我们哪些问题"理论上困难"，但算法设计提供了"实践中高效"的方法。
将问题分解为若干规模较小的子问题，递归求解后合并结果。核心步骤：分解（divide）→ 求解（conquer）→ 合并（combine）。
经典案例 ：
归并排序 ：T ( n ) = 2 T ( n / 2 ) + O ( n ) T ( n ) = 2 T ( n / 2 ) + O ( n ) Θ ( n log n ) Θ ( n log n ) 快速排序 ：T ( n ) = T ( k ) + T ( n − k − 1 ) + O ( n ) T ( n ) = T ( k ) + T ( n − k − 1 ) + O ( n ) Θ ( n log n ) Θ ( n log n ) O ( n 2 ) O ( n 2 ) 快速傅里叶变换（FFT） ：T ( n ) = 2 T ( n / 2 ) + O ( n ) T ( n ) = 2 T ( n / 2 ) + O ( n ) Θ ( n log n ) Θ ( n log n ) Strassen 矩阵乘法 ：T ( n ) = 7 T ( n / 2 ) + O ( n 2 ) T ( n ) = 7 T ( n / 2 ) + O ( n 2 ) O ( n 2 7 ) ≈ O ( n 2.81 ) O ( n l o g 2 7 ) ≈ O ( n 2 . 8 1 ) O ( n 3 ) O ( n 3 ) Karatsuba 乘法 ：大整数乘法的第一个亚三次算法，O ( n 2 3 ) ≈ O ( n 1.585 ) O ( n l o g 2 3 ) ≈ O ( n 1 . 5 8 5 )
动态规划（Dynamic Programming, DP）解决具有最优子结构 （问题最优解包含子问题最优解）和重叠子问题 （子问题被反复求解）的问题。
设计步骤 ：
定义子问题
构建递推关系（状态转移方程）
确定边界条件和计算顺序
实现自底向上或带记忆的自顶向下方
经典案例 ：
最长公共子序列（LCS） ：d p [ i ] [ j ] = max ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j − 1 ] + 1 ) d p [ i ] [ j ] = max ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j − 1 ] + 1 ) O ( m n ) O ( m n ) Floyd-Warshall 最短路径 ：d p [ i ] [ j ] [ k ] = min ( d p [ i ] [ j ] [ k − 1 ] , d p [ i ] [ k ] [ k − 1 ] + d p [ k ] [ j ] [ k − 1 ] ) d p [ i ] [ j ] [ k ] = min ( d p [ i ] [ j ] [ k − 1 ] , d p [ i ] [ k ] [ k − 1 ] + d p [ k ] [ j ] [ k − 1 ] ) O ( n 3 ) O ( n 3 ) 0/1 背包问题 ：d p [ i ] [ w ] = max ( d p [ i − 1 ] [ w ] , d p [ i − 1 ] [ w − w i ] + v i ) d p [ i ] [ w ] = max ( d p [ i − 1 ] [ w ] , d p [ i − 1 ] [ w − w i ] + v i ) O ( n W ) O ( n W ) W W 编辑距离（Edit Distance） ：d p [ i ] [ j ] = min ( d p [ i − 1 ] [ j ] + 1 , d p [ i ] [ j − 1 ] + 1 , d p [ i − 1 ] [ j − 1 ] + cost ) d p [ i ] [ j ] = min ( d p [ i − 1 ] [ j ] + 1 , d p [ i ] [ j − 1 ] + 1 , d p [ i − 1 ] [ j − 1 ] + cost ) O ( m n ) O ( m n ) 矩阵链乘 ：O ( n 3 ) O ( n 3 ) 最长递增子序列（LIS） ：O ( n log n ) O ( n log n ) 贝尔曼-福特（Bellman-Ford） ：O ( V E ) O ( V E )
每一步做出局部最优选择，期望得到全局最优解。贪心算法只在满足贪心选择性质 （贪心选择不破坏子问题的最优性）的问题上正确。
证明贪心正确性"最常用的方法 ：交换论证（Exchange Argument）——证明任何最优解可以通过一系列"交换"转化为贪心解而不降低质量。
经典案例 ：
霍夫曼编码 ：贪心选择出现频率最低的两个字符合并，O ( n log n ) O ( n log n ) 最小生成树（MST） ：
Prim 算法：从顶点出发，每次选择连接已选和未选集的最小边，O ( E log V ) O ( E log V )
Kruskal 算法：将所有边排序，从小到大选择不形成环的边，O ( E log V ) O ( E log V )
Dijkstra 最短路径 ：从源点出发，每次选择距离最小的未处理顶点，O ( ( V + E ) log V ) O ( ( V + E ) log V ) 区间调度（Interval Scheduling） ：按结束时间最早选择不冲突区间，O ( n log n ) O ( n log n ) 哈夫曼编码 ：最优二叉合并树分数背包 ：按性价比（v i / w i v i / w i
通过系统的搜索空间遍历来求解组合优化问题，配合剪枝 避免不必要的探索。
回溯（Backtracking） ：深度优先搜索状态空间树，遇到不可能产生解的节点时回溯。
分支限界（Branch and Bound） ：回溯的优化版本——维护全局最优解下界/上界，当分支的界限劣于当前最优解时剪枝。
经典案例 ：
N皇后问题 ：在 N × N N × N N N O ( N ! ) O ( N ! ) 数独求解 ：回溯+约束传播（AC-3）旅行商精确求解 ：分支限界，对 n ≤ 40 n ≤ 4 0 八数码/十五数码 ：A* 搜索（回溯+启发式）
网络流（Network Flow）是解决分配、匹配、调度问题的强大框架。
核心思想 ：在带源点 s s t t s s t t
经典算法 ：
Ford-Fulkerson ：O ( E ⋅ f ) O ( E ⋅ f ) f f Edmonds-Karp ：BFS 找增广路径，O ( V E 2 ) O ( V E 2 ) Dinic ：分层图+阻塞流，O ( V 2 E ) O ( V 2 E ) Push-Relabel （HLPP）：实际最快的流算法，O ( V 3 ) O ( V 3 )
经典应用 ：
二分图最大匹配 ：匈牙利算法 O ( V E ) O ( V E ) 最小割 ：最大流=最小割定理（Max-Flow Min-Cut Theorem）二部图的最小顶点覆盖 ：Kőnig 定理——在二部图中，最小顶点覆盖大小等于最大匹配大小任务分配 、流量调度 、图像分割 （Graph Cut）
引入随机性来简化问题或突破确定性算法瓶颈。随机化本身不增加计算能力（P = BPP 被广泛信服），但能带来更简单或更高效的实践方案。
类型 ：
拉斯维加斯算法（Las Vegas） ：始终给出正确解，但运行时间是随机变量。如随机化快速排序，期望 O ( n log n ) O ( n log n ) O ( n 2 ) O ( n 2 ) 蒙特卡罗算法（Monte Carlo） ：运行时间固定，但可能以微小概率出错。可通过多次运行降低错误率（错误概率随运行次数指数下降）
经典案例 ：
随机化最小割 ：Karger 算法——每次随机收缩一条边，保留到最后两个顶点即为候选割。O ( n 2 3 n ) O ( n 2 log 3 n ) Ω ( 1 / n 2 ) Ω ( 1 / n 2 ) 素数检测 ：Miller-Rabin 素性测试，ϵ < 1 / 4 ϵ < 1 / 4 k k 4 − k 4 − k 快速排序中随机化枢轴选择 ：避免最坏情况，期望 O ( n log n ) O ( n log n ) 哈希算法 ：Universal Hashing 保证了良好的哈希函数分布最近点对问题 ：随机化算法比分治算法更简单
对 NP 难问题，放弃精确解，寻求多项式时间内得到接近最优 的解。
近似比 ：若算法总能输出一个成本不超过最优解 α α 1 α α 1 α α
多项式时间近似方案（PTAS） ：对任意 ϵ > 0 ϵ > 0 ( 1 + ϵ ) ( 1 + ϵ ) ϵ ϵ 完全多项式时间近似方案（FPTAS） 的运行时间关于 1 / ϵ 1 / ϵ
经典案例 ：
图顶点覆盖 ：2-近似——选择一条未被覆盖的边，将两端点加入解中旅行商问题 （满足三角形不等式）：Christofides 算法，3/2-近似——目前已知最佳集合覆盖 ：ln n ln n 装箱问题 ：首次适应递减（First-Fit Decreasing, FFD），11/9-近似最大割 ：0.5-近似（随机化），0.878-近似（Goemans-Williamson，使用半定规划松弛）k-中心问题 ：2-近似（Gonzalez 算法）子集和问题 ：FPTAS——存在任意精度的近似方案
在输入并非一次性给出的情况下做出决策，未来不可预知。在线算法与离线最优算法的性能比称为竞争比（Competitive Ratio） 。
经典案例 ：
缓存替换（LRU, LFU） ：LRU 的竞争比是 k k k k 在线匹配 ：贪心 1/2-近似，KVV 算法 ( 1 − 1 / e ) ( 1 − 1 / e ) 两级租赁问题（Ski Rental） ：2-竞争——有界前瞻可以改善竞争比在线装箱 ：First-Fit 的竞争比为 2在线二分图匹配 ：在"已知全部顶点但边依次出现"的模型中，Ranking 算法达到 ( 1 − 1 / e ) ( 1 − 1 / e )
参数化复杂性（Parameterized Complexity）研究问题的多个维度的复杂性，而不仅依赖输入规模 n n
核心概念 ：
固定参数可解（FPT） ：以参数 k k O ( f ( k ) ⋅ n c ) O ( f ( k ) ⋅ n c ) f f c c W[1]-难 ：一般认为不比包含子图中的团（Clique）问题更容易——这类问题在参数化意义下也是"困难的"
这意味着某些 NP 完全问题对小的参数是有实用意义的：例如顶点覆盖在 k = 100 k = 1 0 0 O ( 2 k ⋅ n ) O ( 2 k ⋅ n ) k k k k
问题规模
安全的时间复杂度
适用场景
n ≤ 10 n ≤ 1 0 O ( n ! ) O ( n ! ) O ( 2 n 2 n ) O ( 2 n 2 n ) 精确回溯
n ≤ 20 n ≤ 2 0 O ( 2 n ) O ( 2 n ) 状态压缩 DP、bitmask 穷举
n ≤ 100 n ≤ 1 0 0 O ( n 3 ) O ( n 3 ) Floyd、三层循环 DP
n ≤ 1 0 3 n ≤ 1 0 3 O ( n 2 ) O ( n 2 ) 朴素 DP、两两比较
n ≤ 1 0 4 n ≤ 1 0 4 O ( n n ) O ( n n ) 分块、莫队算法
n ≤ 1 0 5 n ≤ 1 0 5 O ( n log n ) O ( n log n ) 排序、分治、BST、线段树
n ≤ 1 0 6 n ≤ 1 0 6 O ( n ) O ( n ) 线性扫描、哈希表、双指针
n ≤ 1 0 8 n ≤ 1 0 8 O ( log n ) O ( log n ) O ( 1 ) O ( 1 ) 二分查找、数学公式、前缀和
大 O O
快速排序 vs 堆排序 ：两者都是 O ( n log n ) O ( n log n ) Strassen 矩阵乘法 ：O ( n 2.81 ) O ( n 2 . 8 1 ) O ( n 3 ) O ( n 3 ) n > 1000 n > 1 0 0 0 哈希表 O ( 1 ) O ( 1 ) ：在冲突严重、哈希函数代价高、Cache Miss 多时，可能比有序数组的二分查找 O ( log n ) O ( log n )
Hugo 的实践笔记 ：O ( log n ) O ( log n ) O ( 1 ) O ( 1 ) 大 O 分析不能替代性能剖析（Profiling） ——先 profile，再优化。
分析类型
含义
示例
最坏情况 对给定规模 n n
快速排序的 O ( n 2 ) O ( n 2 )
平均情况 对给定规模 n n
快速排序的 Θ ( n log n ) Θ ( n log n )
摊还 一个操作序列中每个操作的平均资源消耗
动态数组尾插的 O ( 1 ) O ( 1 )
期望 随机化算法的期望资源消耗
随机化快排的 Θ ( n log n ) Θ ( n log n )
实践建议 ：生产环境中，最坏情况分析比平均情况更重要 ——用户不会遇到你的平均情况，他们只会遇到最坏情况。特别是外部输入可能被精心构造来触发最坏情况（如哈希碰撞攻击、DoS 攻击）。
P vs NP ：千年难题之首。100万美元奖金，50多年来无人攻克NP = co-NP? ：如果成立，则 NP 完全问题存在多项式大小的证明——被认为不太可能P = BPP? ：目前普遍认为 P = BPP（Impagliazzo-Wigderson 定理暗示如果 P ≠ = 唯一游戏猜想（Unique Games Conjecture, UGC） ：如果成立，则许多优化问题的近似比都有精确的下界。如最大割的0.878近似是（也仅仅是最优的）指数时间假设（Exponential Time Hypothesis, ETH） ：3-SAT 不能在 2 o ( n ) 2 o ( n ) 强指数时间假设（SETH） ：3-SAT 不能在 2 ( 1 − ϵ ) n 2 ( 1 − ϵ ) n
量子计算引入了一个新的复杂性类：BQP （Bounded-error Quantum Polynomial time），即量子计算机在多项式时间内以高概率可解的问题。
已知关系：
P ⊆ BPP ⊆ BQP ⊆ PSPACE P ⊆ BPP ⊆ BQP ⊆ PSPACE
Shor 算法 （1994年）：证明了因数分解和离散对数在量子计算机上可在多项式时间内求解（即属于 BQP）。这直接威胁 RSA 和 ECC 等公钥密码系统的安全性——正是因为这一原因，NIST 正在推动后量子密码（Post-Quantum Cryptography, PQC）标准化。
但重要的是：因数分解不认为是 NP 完全的 。这意味着量子计算并非 NP 问题的万能解药——对典型的 NP 完全问题（如 TSP、SAT），量子计算机可能也提供不了指数级别的加速。
Grover 搜索算法 ：在无序数据库中搜索可达到 O ( n ) O ( n ) O ( n ) O ( n ) N = 1 0 6 N = 1 0 6 1 0 6 1 0 6
交互式证明系统（Interactive Proof Systems, IP）扩展了经典证明的概念：一个无限能力的证明者（Prover, Peggy）与一个多项式时间验证者（Verifier, Victor）通过消息交换来完成证明。
令人惊讶的结论：IP = PSPACE （Shamir 定理, 1992年）。这意味着所有 PSPACE 中的问题都有交互式证明协议。注意 IP 显然包含 NP（NP 的验证者可以简单地忽略证明者的交互直接验证证据），但 IP 远强于 NP。
零知识证明（Zero-Knowledge Proof, ZKP） 是 IP 的进一步推广：证明者可以证明一个陈述为真，而不泄露任何额外信息（即零知识）。形式化地说，存在一个模拟器可以在不与证明者交互的情况下生成与真实交互不可区分的对话记录。
经典例子——阿里山洞协议 ：
P 知道一个连通两个入口的密道
V 随机选择一个入口，要求 P 从另一个出口出来
如果 P 知道密道，总能成功；如果不知道，每次只能以 1/2 概率蒙对
重复 t t 2 − t 2 − t
实际应用 ：
区块链扩展 ：zk-SNARKs, zk-STARKs——将大量计算压缩为单一可验证证明隐私保护认证 ：在不泄露密码的情况下证明身份隐私交易 ：Zcash 的匿名交易——向全网证明交易合法，但不泄露发送方、接收方和金额可信计算 ：Intel SGX 的远程验证
通信复杂性研究分布式计算中所需的信息交换量，是并行计算、网络协议和数据库查询优化的理论基础。
核心模型 ：两个参与者 Alice 和 Bob 各自拥有输入 x x y y f ( x , y ) f ( x , y )
完美匹配的下界 ：f ( x , y ) = E Q ( x , y ) f ( x , y ) = E Q ( x , y ) Ω ( n ) Ω ( n )
算法与复杂性理论构建了计算的数学基础，它告诉我们：
可计算性 ：并非所有问题都能用算法解决——停机问题、希尔伯特第十问题等划定了计算的极限可处理性 ：即使是可计算问题，也存在天然的"难易分界线"——P 类问题可有效求解，NP 完全问题可能本质上困难（如果 P ≠ = 实用策略 ：对于"难"的问题，近似算法（PTAS, FPTAS）、随机化（蒙特卡罗、拉斯维加斯）、参数化算法和启发式方法提供了替代路径持续挑战 ：量子计算（BQP）、交互式证明（IP, ZK）、通信复杂性等新模型不断扩展我们对"计算"本质的理解实践为王 ：大 O 分析是起点而非终点——常数因子、缓存行为、输入分布等现实因素同样重要
从日常编程中的算法选择到密码学的安全基础，从大数据处理到人工智能的实现边界，复杂性理论的影响无处不在。理解它，不是去解决 P vs NP（虽然这很诱人），而是培养对"计算本质"的深刻直觉——知道什么可行、什么不可行、以及为什么。
此页面是数学知识库中计算数学模块的一部分。相关页面：数学知识库索引 、数理逻辑 、集合论 、概率论