在学习算法时，我们肯定会关注效率。于是我们会分析时间复杂度，比如 \(O(n)\)、\(O(n\log n)\)、\(O(n^2)\)。
但这只是算法分析的一半。另一半问题是：这个问题本身最快能做到多快？也就是说，在某个给定的计算模型下，不管你设计什么算法，它都不可能突破某个理论下界。
如果一个算法的上界和问题的下界在渐近意义上相同，那么这个算法就是最优算法。
例如，比较排序问题可以被证明有下界：
\[\Omega(n\log n) \]
归并排序、堆排序的时间复杂度是：
\[O(n\log n) \]
所以它们在比较排序模型下是渐近最优的。
换句话说，要证明归并排序最优，不能只说它优于其他算法，还要证明比较排序这个问题本身不可能比 \(\Omega(n\log n)\) 更快。
下界这个符号用得不多，它写作：
\[\Omega(f(n)) \]
它表示至少需要多少时间。通俗地说，\(O(n^2)\) 是不超过 \(n^2\)，\(\Omega(n^2)\) 是不低于 \(n^2\)。
如果一个算法是 \(O(f(n))\)，而问题本身的复杂度满足 \(\Omega(f(n))\)
那么我们就可以说这个算法是渐近最优的。也就是：
\[O(f(n)) \quad \text{和} \quad \Omega(f(n)) \]
匹配。这就是所谓的最优算法（optimal algorithm）。
当然，这里的最优是渐近意义上的最优。比如有很多排序算法都是 \(O(n\log n)\)，即使常数有差距，但从渐近复杂度角度看，它们都达到了比较排序问题的理论下界。
还要注意：下界通常是相对于某个计算模型、输入类型和输出要求而言的。同一个问题，在比较模型、代数决策树模型、RAM 模型或允许哈希的模型下，可能有不同的复杂度结论。
有些下界不需要复杂数学，也不需要建立计算模型，靠直觉就能推出。
给定一个无序数组，找出其中最大值。假设数组中有 \(n\) 个元素。
由于任何算法都必须至少看每个元素一次。否则，如果某个元素完全没被检查过，它就有可能是最大值，算法就可能出错。
所以这个问题的下界是：\(\Omega(n)\)
而直接线性扫描，算法也正是 \(O(n)\)。所以上界和下界匹配，线性扫描是渐近最优的。更精确地说，至少需要 \(n-1\) 次比较。
假定问题是两个 \(n\times n\) 矩阵相乘，结果仍然是一个 \(n\times n\) 矩阵。
结果矩阵有：\(n^2\) 个元素。即使不考虑计算过程，只是把结果写出来，也至少需要写出 \(n^2\) 个数。
所以矩阵乘法至少需要：\(\Omega(n^2)\)。这是一个由输出规模决定的下界。
算法上，经典矩阵乘法是 \(O(n^3)\)，Strassen 等算法可以更快。目前最好已知的平方矩阵乘法算法可以做到约 \(O(n^{2.37})\)，但这只是已知上界，不代表已经证明最优。无论如何，只要问题要求显式写出整个结果矩阵，就不可能低于输出本身的规模 \(\Omega(n^2)\)。
为了证明更复杂的下界，我们需要一个模型。一个常见工具是 decision tree，也就是决策树。
很多算法本质上是在不断做判断：
if x < a[mid]:
go left
else:
go right
或者：
if a[i] < a[j]:
...
else:
...
决策树就是把这些分支判断画成一棵二叉树。
每个内部节点表示一次判断，每条边表示判断结果，每个叶子节点表示最终输出。
比如：
compare x and A[mid]
/ \
x < A[mid] x >= A[mid]
/ \
continue continue
在这种情况下，我们会发现：最坏情况下比较次数 = 决策树高度
考虑问题：在长度为 \(n\) 的有序数组中查找某个元素。
我们知道，二分查找需要 \(O(\log n)\)，那么它是不是最优的？答案是：是的。
在决策树模型中，每次比较最多只能把当前可能情况分成两部分。高度为 \(h\) 的二叉树最多有 \(2^h\) 个叶子。
因此，如果问题至少有 \(n\) 种不同可能结果，那么必须满足：\(2^h \ge n\)，所以 \(h \ge \log n\)
也就是说，任何算法在最坏情况下都至少需要：\(\Omega(\log n)\) 次比较。精确比较次数会依赖具体任务定义，比如是否允许查找失败、一次比较是二路还是三路、输出是位置还是 yes/no；但渐近下界都是 \(\Omega(\log n)\)。
这说明二分查找的 \(O(\log n)\) 和问题下界 \(\Omega(\log n)\) 匹配，是最优的。
排序是算法课中最经典的下界证明。问题是：给定 \(n\) 个不同元素，只通过比较操作把它们排序。
对于 \(n\) 个不同元素，可能的排列一共有 \(n!\) 种。排序算法必须能够区分所有这些可能的答案，才能输出正确顺序。
在比较排序的决策树中，每个内部节点是一次比较，比如每一次比较判断：
\[x_i < x_j? \]
最多产生两个分支。注意，这并不意味着每次比较都能刚好排除一半结果；下界证明真正依赖的是：高度为 \(h\) 的二叉决策树最多只有 \(2^h\) 个叶子。最终，每个叶子节点对应一种可能的最终排列判断结果。
同理，高度为 \(h\) 的决策树要满足 \(2^h \ge n!\)，两边取对数得 \(h \ge \log(n!)\)
而根据 Stirling 近似，有：
\[\log(n!)=\Omega(n\log n) \]
这就是比较排序的核心下界。因此，归并排序、堆排序这类 \(O(n\log n)\) 的比较排序算法已经是渐近最优的。
比较排序要求我们只能进行元素比较，根据相对大小来排出序列，不利用待排元素的特殊性质。如果想突破 \(n\log n\)，就必须离开纯比较模型，例如桶排序、基数排序。这些算法利用了输入值范围或数字结构，而不只是比较两个元素的大小。
排序算法的决策树只做比较，但有些算法会做更复杂的判断。于是我们引入 algebraic decision tree，也就是代数决策树。
在代数决策树中，每个内部节点可以测试一个代数表达式：
\[f(x_1,x_2,\dots,x_n) : 0 \]
其中 \(:\) 可以是：
\[=,\ <,\ \le \]
也就是说，每个节点可以测试某个多项式条件是否成立，例如 \(f(x_1,\dots,x_n)<0\)、\(f(x_1,\dots,x_n)=0\) 或 \(f(x_1,\dots,x_n)\le 0\)，然后根据测试结果走向某个子树。最终叶子节点给出答案 yes 或 no。
为了和前面的二叉决策树保持一致，可以把每次测试看成产生常数个分支。若采用三路符号判断，叶子数上界会从 \(2^h\) 变成 \(3^h\)，但这只影响常数，不影响后面的渐近下界结论。
这是普通比较决策树的扩展，普通比较决策树是代数决策树的特例。
而如果每个测试函数 \(f\) 都是一次函数：
\[f(x_1,\dots,x_n)=a_1x_1+a_2x_2+\cdots+a_nx_n+b \]
那么这棵树叫做 linear algebraic decision tree，也就是线性代数决策树。
普通比较 \(x_i < x_j\) 等价于 \(x_i-x_j<0\)，所以它属于线性代数决策树。
三者之间的关系可以写成：
\[\text{比较决策树} \subseteq \text{线性代数决策树} \subseteq \text{代数决策树} \]
模型越强，证明下界越难。如果我们能在更强的代数决策树模型中证明某个问题仍然需要 \(\Omega(n\log n)\)，那么这个下界就更有说服力。
决策问题可以转化成几何问题。一个决策问题的答案只有两种：yes / no。假设输入是 \(n\) 个实数：
\[x_1,x_2,\dots,x_n \]
我们可以把它看成 \(n\) 维欧氏空间中的一个点：
\[p=(x_1,x_2,\dots,x_n)\in E^n \]
所有答案为 yes 的输入点组成一个集合：
\[W\subseteq E^n \]
于是，属于 \(W\) 即代表决策 yes，不属于 \(W\) 即代表决策 no。如果一棵代数决策树 \(T\) 满足：
\[p\in W \Rightarrow T \text{ 到达 yes 叶子} \]
并且：
\[p\notin W \Rightarrow T \text{ 到达 no 叶子} \]
那么就说这棵树接受集合 \(W\)，或者说它决定了 \(W\) 的成员关系。
这样就把算法问题变成了几何空间中的区域划分问题。
\(\#W\) 通常表示集合 \(W\) 的连通分支数量，表示的是：yes 区域被分成了多少块互不连通的区域。
直观上，如果 \(W\) 有很多互不连通的块，那么算法就必须有足够复杂的判断过程来区分这些块。
所以，\(\#W\) 越大，问题通常越难。
如果 \(W\subseteq E^n\)，并且线性决策树 \(T\) 接受集合 \(W\)，那么 \(T\) 的高度至少是：
\[\lceil \log(\#W)\rceil \]
因为高度为 \(h\) 的二叉树最多有 \(2^h\) 个叶子。如果 \(W\) 有 \(\#W\) 个连通分支，那么决策树至少要有足够多叶子来区分这些不同区域。
所以 \(2^h\ge \#W\)，并推出 \(h\ge \log(\#W)\)
进一步推广到代数决策树。设 \(W\subseteq E^n\)，\(d\) 是固定正整数，那么任何 order \(d\) 的代数决策树 \(T\) 如果接受 \(W\)，其高度至少是：
\[\Omega(\log \#W-n) \]
这里的 order \(d\) 表示每个测试函数 \(f\) 是次数不超过 \(d\) 的多项式。也就是说，算法每一步可以做固定次数的多项式判断，但次数 \(d\) 是常数。
这个定理告诉我们：即使允许更强的代数判断，只要 yes 区域 \(W\) 的连通分支足够多，决策树的高度仍然必须很大。
核心思想仍然是：
\[\text{连通分支多} \Rightarrow \text{需要很多叶子} \Rightarrow \text{决策树高度大} \Rightarrow \text{算法下界高} \]
Element Uniqueness，也常称为 Element Distinctness，是一个非常重要的下界基准问题。问题是：给定 \(n\) 个实数，判断它们是否两两不同。
形式化地说，就是判断：
\[x_i\ne x_j,\quad \forall i\ne j \]
答案为 yes 的集合是：
\[W={(x_1,\dots,x_n)\mid x_i\ne x_j,\forall i\ne j} \]
这个集合会被很多超平面切开：
\[x_i=x_j \]
这些超平面把空间划分成不同区域。每个区域对应一种严格大小顺序：
\[x_{\pi(1)}<x_{\pi(2)}<\cdots<x_{\pi(n)} \]
这样的顺序共有 \(n!\) 种。因此 \(\#W=n!\)
利用代数决策树下界，可以得到：
\[\Omega(\log(n!)-n)=\Omega(n\log n) \]
这就是 Element Uniqueness 在固定次数代数决策树模型下的下界。这里必须强调模型限制：这个结论不能理解为“现实编程中不能用哈希表”。如果输入是可哈希对象或有合适的整数模型，哈希方法可以在期望线性时间内判断是否有重复；只是这类操作不属于当前讨论的代数决策树模型。
这个问题之所以重要，是因为很多几何问题的下界都可以通过它来证明。
\(A\propto_n B\) 表示：问题 \(A\) 可以在线性时间内归约到问题 \(B\)。
也就是说，我们能做到：
更常见的符号写作
\[A\le_{\text{linear}}B \]
规约的意义是：如果 \(A\) 很难，而 \(A\) 又能线性归约到 \(B\)，那么 \(B\) 至少也一样难。
假设 \(B\) 有一个特别快的算法，比如快于 \(n\log n\)，那么我们就可以用下面方式快速解决 \(A\)：
solve_A(input):
input_B = transform_A_to_B(input) # O(n)
answer_B = solve_B(input_B) # 假设很快
answer_A = transform_B_to_A(answer_B) # O(n)
return answer_A
如果 \(A\) 已经被证明需要 \(\Omega(n\log n)\)，那么 \(B\) 就不可能更快。否则会导致 \(A\) 的下界被突破，产生矛盾。
凸包问题是：给定平面上的 \(n\) 个点，求包含所有点的最小凸多边形。
它的下界可以通过排序归约得到。给定 \(n\) 个实数：
\[x_1,x_2,\dots,x_n \]
我们把每个数映射成平面上的点 \(p_i=(x_i,x_i^2)\)，这些点都在抛物线 \(y=x^2\) 上。
如果凸包算法输出的是按边界顺序排列的凸包顶点，那么求出这些点的凸包后，凸包上的点会按照 \(x\) 坐标顺序排列。于是，我们可以从凸包输出中读出原来这些数的排序结果。
所以有：
\[\text{Sorting}\le_{\text{linear}}\text{Convex Hull} \]
而排序在比较模型下已经需要 \(\Omega(n\log n)\)，所以在相应的代数决策树模型和有序输出要求下，凸包也需要 \(\Omega(n\log n)\)。这说明，常见的 \(O(n\log n)\) 凸包算法，比如 Graham Scan、Andrew Monotone Chain，在最坏情况下的渐近意义上也是最优的。
最近点对问题是：给定平面上的 \(n\) 个点，找出距离最近的两个点。
它的下界可以通过 Element Uniqueness 归约得到。给定 \(n\) 个实数：
\[x_1,x_2,\dots,x_n \]
构造平面点集 \(p_i=(x_i,0)\)
如果存在重复元素 \(x_i=x_j\)，那么对应的两个点重合，最近距离就是 \(0\)；如果所有元素都不同，那么任意两个点之间的距离都大于 \(0\)。
因此，只要能解决最近点对问题，我们就能判断是否存在重复元素。
\[\text{Element Uniqueness} \le_{\text{linear}} \text{Closest Pair} \]
在代数决策树模型下，Element Uniqueness 需要 \(\Omega(n\log n)\)，所以最近点对也需要 \(\Omega(n\log n)\)。
经典最近点对算法也正是 \(O(n\log n)\)。
欧氏最小生成树问题是：给定平面上的 \(n\) 个点，以点之间的欧氏距离为边权，求最小生成树。
它的下界可以通过最近点对归约得到。因为在完全图的欧氏距离权重下，欧氏最小生成树中的最短边一定对应某个最近点对。如果有一个算法可以很快求出欧氏最小生成树，我们就可以从生成树的最短边中读出最近点对。
所以有：
\[\text{Closest Pair} \le_{\text{linear}} \text{Euclidean MST} \]
因此，在相同计算模型下，欧氏最小生成树也有 \(\Omega(n\log n)\) 下界。
类似的证明套路还可以用于很多计算几何问题：先选择一个已经证明困难的母问题，再把它线性时间归约到目标问题。只要归约过程不偷渡额外计算，母问题的下界就会传递给目标问题。
这说明，代数决策树和线性时间归约是一套更通用的下界证明方法。
当我们看到一个问题已经有算法时，还能不能优化？有时还可以额外优化，但有时不行，因为它本身有理论下界。除非算法能利用额外条件，例如数据部分有序、数据是小范围整数、数据分布有特殊性，或者计算模型允许更强的操作。例如对于整数，基数排序可以在合适条件下做到线性。
决策树模型可以证明排序下界，代数决策树模型可以证明 Element Uniqueness 下界。接着，通过线性时间归约，把这些下界传递给其他问题：
\[\text{Sorting} \le_{\text{linear}} \text{Convex Hull} \]
\[\text{Element Uniqueness} \le_{\text{linear}} \text{Closest Pair} \]
\[\text{Closest Pair} \le_{\text{linear}} \text{Euclidean MST} \]
通过规约，我们可以从重要的母问题出发，推导出更多问题的下界。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。