在学习算法时我们肯定会关注效率。于是我们会分析时间复杂度比如 ()O(n)、(log)O(nlogn)、(2)O(n2)。但这只是算法分析的一半。另一半问题是这个问题本身最快能做到多快也就是说在某个给定的计算模型下不管你设计什么算法它都不可能突破某个理论下界。如果一个算法的上界和问题的下界在渐近意义上相同那么这个算法就是最优算法。例如比较排序问题可以被证明有下界Ω(log)Ω(nlogn)归并排序、堆排序的时间复杂度是(log)O(nlogn)所以它们在比较排序模型下是渐近最优的。换句话说要证明归并排序最优不能只说它优于其他算法还要证明比较排序这个问题本身不可能比 Ω(log)Ω(nlogn) 更快。上界、下界和最优算法下界这个符号用得不多它写作Ω(())Ω(f(n))它表示至少需要多少时间。通俗地说(2)O(n2) 是不超过 2n2Ω(2)Ω(n2) 是不低于 2n2。如果一个算法是 (())O(f(n))而问题本身的复杂度满足 Ω(())Ω(f(n))那么我们就可以说这个算法是渐近最优的。也就是(())和Ω(())O(f(n))和Ω(f(n))匹配。这就是所谓的最优算法optimal algorithm。当然这里的最优是渐近意义上的最优。比如有很多排序算法都是 (log)O(nlogn)即使常数有差距但从渐近复杂度角度看它们都达到了比较排序问题的理论下界。还要注意下界通常是相对于某个计算模型、输入类型和输出要求而言的。同一个问题在比较模型、代数决策树模型、RAM 模型或允许哈希的模型下可能有不同的复杂度结论。用直觉平凡的下界有些下界不需要复杂数学也不需要建立计算模型靠直觉就能推出。无序数组找最大值给定一个无序数组找出其中最大值。假设数组中有 n 个元素。由于任何算法都必须至少看每个元素一次。否则如果某个元素完全没被检查过它就有可能是最大值算法就可能出错。所以这个问题的下界是Ω()Ω(n)而直接线性扫描算法也正是 ()O(n)。所以上界和下界匹配线性扫描是渐近最优的。更精确地说至少需要 −1n−1 次比较。矩阵乘法假定问题是两个 ×n×n 矩阵相乘结果仍然是一个 ×n×n 矩阵。结果矩阵有2n2 个元素。即使不考虑计算过程只是把结果写出来也至少需要写出 2n2 个数。所以矩阵乘法至少需要Ω(2)Ω(n2)。这是一个由输出规模决定的下界。算法上经典矩阵乘法是 (3)O(n3)Strassen 等算法可以更快。目前最好已知的平方矩阵乘法算法可以做到约 (2.37)O(n2.37)但这只是已知上界不代表已经证明最优。无论如何只要问题要求显式写出整个结果矩阵就不可能低于输出本身的规模 Ω(2)Ω(n2)。决策树把算法的分支过程画成树为了证明更复杂的下界我们需要一个模型。一个常见工具是 decision tree也就是决策树。很多算法本质上是在不断做判断if x a[mid]:go leftelse:go right或者if a[i] a[j]:...else:...决策树就是把这些分支判断画成一棵二叉树。每个内部节点表示一次判断每条边表示判断结果每个叶子节点表示最终输出。比如compare x and A[mid]/ \x A[mid] x A[mid]/ \continue continue在这种情况下我们会发现最坏情况下比较次数 决策树高度有序查找考虑问题在长度为 n 的有序数组中查找某个元素。我们知道二分查找需要 (log)O(logn)那么它是不是最优的答案是是的。在决策树模型中每次比较最多只能把当前可能情况分成两部分。高度为 ℎh 的二叉树最多有 2ℎ2h 个叶子。因此如果问题至少有 n 种不同可能结果那么必须满足2ℎ≥2h≥n所以 ℎ≥logh≥logn也就是说任何算法在最坏情况下都至少需要Ω(log)Ω(logn) 次比较。精确比较次数会依赖具体任务定义比如是否允许查找失败、一次比较是二路还是三路、输出是位置还是 yes/no但渐近下界都是 Ω(log)Ω(logn)。这说明二分查找的 (log)O(logn) 和问题下界 Ω(log)Ω(logn) 匹配是最优的。比较排序排序是算法课中最经典的下界证明。问题是给定 n 个不同元素只通过比较操作把它们排序。对于 n 个不同元素可能的排列一共有 !n! 种。排序算法必须能够区分所有这些可能的答案才能输出正确顺序。在比较排序的决策树中每个内部节点是一次比较比如每一次比较判断?xixj?最多产生两个分支。注意这并不意味着每次比较都能刚好排除一半结果下界证明真正依赖的是高度为 ℎh 的二叉决策树最多只有 2ℎ2h 个叶子。最终每个叶子节点对应一种可能的最终排列判断结果。同理高度为 ℎh 的决策树要满足 2ℎ≥!2h≥n!两边取对数得 ℎ≥log(!)h≥log(n!)而根据 Stirling 近似有log(!)Ω(log)log(n!)Ω(nlogn)这就是比较排序的核心下界。因此归并排序、堆排序这类 (log)O(nlogn) 的比较排序算法已经是渐近最优的。比较排序要求我们只能进行元素比较根据相对大小来排出序列不利用待排元素的特殊性质。如果想突破 lognlogn就必须离开纯比较模型例如桶排序、基数排序。这些算法利用了输入值范围或数字结构而不只是比较两个元素的大小。代数决策树和线性代数决策树排序算法的决策树只做比较但有些算法会做更复杂的判断。于是我们引入 algebraic decision tree也就是代数决策树。在代数决策树中每个内部节点可以测试一个代数表达式(1,2,…,):0f(x1,x2,…,xn):0其中 :: 可以是, , ≤, , ≤也就是说每个节点可以测试某个多项式条件是否成立例如 (1,…,)0f(x1,…,xn)0、(1,…,)0f(x1,…,xn)0 或 (1,…,)≤0f(x1,…,xn)≤0然后根据测试结果走向某个子树。最终叶子节点给出答案 yes 或 no。为了和前面的二叉决策树保持一致可以把每次测试看成产生常数个分支。若采用三路符号判断叶子数上界会从 2ℎ2h 变成 3ℎ3h但这只影响常数不影响后面的渐近下界结论。这是普通比较决策树的扩展普通比较决策树是代数决策树的特例。而如果每个测试函数 f 都是一次函数(1,…,)1122⋯f(x1,…,xn)a1x1a2x2⋯anxnb那么这棵树叫做 linear algebraic decision tree也就是线性代数决策树。普通比较 xixj 等价于 −0xi−xj0所以它属于线性代数决策树。三者之间的关系可以写成比较决策树⊆线性代数决策树⊆代数决策树比较决策树⊆线性代数决策树⊆代数决策树模型越强证明下界越难。如果我们能在更强的代数决策树模型中证明某个问题仍然需要 Ω(log)Ω(nlogn)那么这个下界就更有说服力。决策问题与集合决策问题可以转化成几何问题。一个决策问题的答案只有两种yes / no。假设输入是 n 个实数1,2,…,x1,x2,…,xn我们可以把它看成 n 维欧氏空间中的一个点(1,2,…,)∈p(x1,x2,…,xn)∈En所有答案为 yes 的输入点组成一个集合⊆W⊆En于是属于 W 即代表决策 yes不属于 W 即代表决策 no。如果一棵代数决策树 T 满足∈⇒ 到达 yes 叶子p∈W⇒T 到达 yes 叶子并且∉⇒ 到达 no 叶子p∈/W⇒T 到达 no 叶子那么就说这棵树接受集合 W或者说它决定了 W 的成员关系。这样就把算法问题变成了几何空间中的区域划分问题。连通分支数量##W 通常表示集合 W 的连通分支数量表示的是yes 区域被分成了多少块互不连通的区域。直观上如果 W 有很多互不连通的块那么算法就必须有足够复杂的判断过程来区分这些块。所以##W 越大问题通常越难。线性决策树的下界如果 ⊆W⊆En并且线性决策树 T 接受集合 W那么 T 的高度至少是⌈log(#)⌉⌈log(#W)⌉因为高度为 ℎh 的二叉树最多有 2ℎ2h 个叶子。如果 W 有 ##W 个连通分支那么决策树至少要有足够多叶子来区分这些不同区域。所以 2ℎ≥#2h≥#W并推出 ℎ≥log(#)h≥log(#W)固定次数代数决策树的下界进一步推广到代数决策树。设 ⊆W⊆End 是固定正整数那么任何 order d 的代数决策树 T 如果接受 W其高度至少是Ω(log#−)Ω(log#W−n)这里的 order d 表示每个测试函数 f 是次数不超过 d 的多项式。也就是说算法每一步可以做固定次数的多项式判断但次数 d 是常数。这个定理告诉我们即使允许更强的代数判断只要 yes 区域 W 的连通分支足够多决策树的高度仍然必须很大。核心思想仍然是连通分支多⇒需要很多叶子⇒决策树高度大⇒算法下界高连通分支多⇒需要很多叶子⇒决策树高度大⇒算法下界高Element Uniqueness 问题Element Uniqueness也常称为 Element Distinctness是一个非常重要的下界基准问题。问题是给定 n 个实数判断它们是否两两不同。形式化地说就是判断≠,∀≠xixj,∀ij答案为 yes 的集合是(1,…,)∣≠,∀≠W(x1,…,xn)∣xixj,∀ij这个集合会被很多超平面切开xixj这些超平面把空间划分成不同区域。每个区域对应一种严格大小顺序(1)(2)⋯()xπ(1)xπ(2)⋯xπ(n)这样的顺序共有 !n! 种。因此 #!#Wn!利用代数决策树下界可以得到Ω(log(!)−)Ω(log)Ω(log(n!)−n)Ω(nlogn)这就是 Element Uniqueness 在固定次数代数决策树模型下的下界。这里必须强调模型限制这个结论不能理解为“现实编程中不能用哈希表”。如果输入是可哈希对象或有合适的整数模型哈希方法可以在期望线性时间内判断是否有重复只是这类操作不属于当前讨论的代数决策树模型。这个问题之所以重要是因为很多几何问题的下界都可以通过它来证明。线性时间归约把困难传递出去∝A∝nB 表示问题 A 可以在线性时间内归约到问题 B。也就是说我们能做到在线性时间内把 A 的输入转换成 B 的输入调用 B 的算法在线性时间内把 B 的结果转换回 A 的答案更常见的符号写作≤linearA≤linearB规约的意义是如果 A 很难而 A 又能线性归约到 B那么 B 至少也一样难。假设 B 有一个特别快的算法比如快于 lognlogn那么我们就可以用下面方式快速解决 Asolve_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 已经被证明需要 Ω(log)Ω(nlogn)那么 B 就不可能更快。否则会导致 A 的下界被突破产生矛盾。凸包问题的下界凸包问题是给定平面上的 n 个点求包含所有点的最小凸多边形。它的下界可以通过排序归约得到。给定 n 个实数1,2,…,x1,x2,…,xn我们把每个数映射成平面上的点 (,2)pi(xi,xi2)这些点都在抛物线 2yx2 上。如果凸包算法输出的是按边界顺序排列的凸包顶点那么求出这些点的凸包后凸包上的点会按照 x 坐标顺序排列。于是我们可以从凸包输出中读出原来这些数的排序结果。所以有Sorting≤linearConvex HullSorting≤linearConvex Hull而排序在比较模型下已经需要 Ω(log)Ω(nlogn)所以在相应的代数决策树模型和有序输出要求下凸包也需要 Ω(log)Ω(nlogn)。这说明常见的 (log)O(nlogn) 凸包算法比如 Graham Scan、Andrew Monotone Chain在最坏情况下的渐近意义上也是最优的。最近点对问题的下界最近点对问题是给定平面上的 n 个点找出距离最近的两个点。它的下界可以通过 Element Uniqueness 归约得到。给定 n 个实数1,2,…,x1,x2,…,xn构造平面点集 (,0)pi(xi,0)如果存在重复元素 xixj那么对应的两个点重合最近距离就是 00如果所有元素都不同那么任意两个点之间的距离都大于 00。因此只要能解决最近点对问题我们就能判断是否存在重复元素。Element Uniqueness≤linearClosest PairElement Uniqueness≤linearClosest Pair在代数决策树模型下Element Uniqueness 需要 Ω(log)Ω(nlogn)所以最近点对也需要 Ω(log)Ω(nlogn)。经典最近点对算法也正是 (log)O(nlogn)。欧氏最小生成树问题的下界欧氏最小生成树问题是给定平面上的 n 个点以点之间的欧氏距离为边权求最小生成树。它的下界可以通过最近点对归约得到。因为在完全图的欧氏距离权重下欧氏最小生成树中的最短边一定对应某个最近点对。如果有一个算法可以很快求出欧氏最小生成树我们就可以从生成树的最短边中读出最近点对。所以有Closest Pair≤linearEuclidean MSTClosest Pair≤linearEuclidean MST因此在相同计算模型下欧氏最小生成树也有 Ω(log)Ω(nlogn) 下界。更多问题的下界
