算法研究的终极追问往往不是“这个算法有多快”而是“这个问题到底有多难”。当我们为一个问题反复优化算法却收效甚微时究竟是我们的技巧不够还是问题本身就有一道不可逾越的壁垒下界理论要回答的正是这个问题。一、下界的概念与意义下界指的是对于某个问题任何算法在最坏情况下至少需要消耗的资源量。若一个算法的复杂度恰好等于问题的下界我们就说该算法是最优的——在渐进意义下不可能再有本质改进。下界是面向问题的而非面向某个具体算法。证明下界通常比设计算法困难得多因为它需要对“所有可能的算法”做出论断。为此我们需要借助计算模型来限定算法的行为空间——图灵机模型定义了可计算性的边界而判定树模型则为基于比较的算法划定了效率的天花板。二、判定树模型与基于比较的排序下界考虑排序问题给定n个互异的元素通过两两比较来确定它们的全序关系。任何仅依赖元素间比较操作来确定顺序的排序算法都可以被建模为一棵判定树。判定树是一棵二叉树每个内部节点代表一次元素比较形如 aiajaiaj左分支表示比较结果为真右分支表示结果为假。每个叶节点代表一个确定的排序结果。算法从根节点开始根据比较结果沿树下降直至抵达某个叶节点输出该叶节点对应的排列。对于给定的n判定树必须包含至少 n!n! 个叶节点——因为n个元素的所有可能排列都必须被区分。设判定树的高度为h即从根到叶的最长路径长度也即算法的最坏情况比较次数一棵高度为h的二叉树至多有 2h2h 个叶节点。因此有不等式2h≥n!2h≥n!两边取对数h≥log2(n!)h≥log2(n!)利用斯特林公式 n!≈2πn⋅(n/e)nn!≈2πn⋅(n/e)n取对数后得 log(n!)nlogn−nlogeΘ(logn)log(n!)nlogn−nlogeΘ(logn)因此hΩ(nlogn)hΩ(nlogn)这就是基于比较的排序问题的下界。归并排序和堆排序的最坏情况复杂度均为 O(nlogn)O(nlogn)碰触到了这个下界因此它们是基于比较的排序算法中的最优者。判定树模型的威力在于它的普适性——它不针对归并排序或快速排序而是对所有可能的基于比较的排序算法同时生效。类似的判定树论证也可用于证明查找问题Ω(logn)Ω(logn)、最接近点对问题等领域的下界。三、P与NP两个最重要的复杂度类如果说下界是在问题之间划出效率的等级那么复杂度类则是在更宏观的尺度上对问题进行分类。其中最基本、也最核心的两个类是P和NP。P类可由确定型图灵机在多项式时间内判定的所有问题的集合。通俗地说这些问题存在多项式时间算法。排序、最短路径、最大流都属于P。NP类可由非确定型图灵机在多项式时间内判定的所有问题的集合。等价地说对于NP中的任意问题若有人给出了一个解称为证书我们可以在多项式时间内验证这个解是否正确。哈密顿回路问题、布尔可满足性问题SAT、背包问题的判定版本均属于NP。显然 P⊆NPP⊆NP因为能在多项式时间内求解的问题自然也能在多项式时间内验证。但反过来NP⊆PNP⊆P 是否成立也就是那个著名的P vs. NP问题——它是当代理论计算机科学最核心的未解难题也是千禧年七大数学难题之一。绝大多数研究者相信 P≠NPPNP即确实存在一些“验证容易、求解困难”的问题但至今无人能给出严格证明。四、NP完全性最难的NP问题在NP类内部有一组处于“难度制高点”的问题称为NP完全问题。一个问题 ΠΠ 是NP完全的需满足两个条件一是 ΠΠ 本身属于NP二是NP中的每一个问题都可以在多项式时间内归约到 ΠΠ。这意味着如果任何一个NP完全问题被证明属于P则整个PNP。Cook于1971年证明了第一个NP完全问题——布尔可满足性问题SAT这个结果被称为Cook-Levin定理。此后Karp通过多项式时间归约将21个经典组合优化问题包括01背包的判定版本、顶点覆盖、团问题、哈密顿回路等全部纳入NP完全行列。至今已发现数千个NP完全问题遍布图论、调度、规划、生物信息学等众多领域。NP完全性的实践意义是当你遇到一个看似棘手的组合优化问题时首先应判断它是否NP完全。如果是那么寻找多项式时间的精确算法极可能是徒劳的除非PNP更务实的策略是转向近似算法、参数化算法或启发式方法——这正是后续篇章将要展开的方向。五、更广阔的下界视野判定树模型给出的下界适用于基于比较的算法但并非所有问题都受此限制。基数排序就跳出了“只做比较”的假设利用元素的整数表示达到 O(n)O(n) 的时间复杂度规避了 Ω(nlogn)Ω(nlogn) 的下界。这提醒我们下界的成立依赖于对计算模型的假设改变模型就可能突破下界。同样在NP完全性的讨论中我们默认了图灵机模型。量子计算模型下的复杂度类BQP与经典P和NP的关系至今仍是活跃的研究前沿。本篇为后续深入图论算法做好了理论铺垫。下一篇我们将从图的表示与遍历算法开始用BFS和DFS的实际操作来感受同样是多项式时间不同的算法结构可以挖掘出图的多幺丰富的性质。
