动机
对幂次代价项所做的精确递归树计算表明,主导工作量可能来自三种不同的来源。实际算法的代价项往往只知道渐近界,或者带有对数因子。更一般的定理可以处理这些情形,但其假设不可省略:若代价项发生振荡,则仅仅根代价项很大,并不能阻止某个更小的子问题具有更大的代价项。
我们在除数的幂次上证明一个常见形式。该定理并不是适用于子问题规模不相等、或任意带向下取整与向上取整的递推的通用规则。配套的递归树单元单独处理了一个平衡取整的例子。
定义
定义 1.4.1
(幂次上的递推式)
固定整数 、,并令 。对于 ,,令 ,且
其中 在这些幂次上非负。所有渐近界均指 时的界,其中 以及假设中的常数保持固定。 表示任意一个大于一的固定底数的对数。
定义 1.4.2
(正则性条件)
第三种情形中使用的正则性条件是:存在 ,使得对所有充分大的 的幂次,
它比较的是一个节点的所有子节点的代价项总和与该节点自身的代价项,而不是仅仅在根处将 与某个幂函数相比较。
定理
定理 1.4.3
(除数幂次上的主定理)
在上述定义下:
- 若对某个 有 ,则 。
- 若对某个固定的 有 ,则 。
- 若对某个 有 ,且正则性条件成立,则 。
定理 1.4.4
(逐层求和恒等式)
对于 ,精确的递推给出
证明思路
证明
(逐层求和:恒等式与三种情形)
展开递推可知,第 层有 个规模为 的节点,并且共有 个叶子,由此证明该恒等式。由于 ,仅叶子就已给出阶为 的正下界。
在情形 1 中,适当放大常数以涵盖有限多个较小的幂次之后,每一层的代价至多为
对 求和,由于它被一个收敛的几何级数所控制,故得 。叶子提供了相应的下界。
在情形 2 中,忽略最小规模的有限多层,因为在这些层上渐近不等式未必已经成立。在其余范围内,第 层的总代价项介于 的两个常数倍之间。对于固定的 ,有 :上界为 ,而后一半的项在相差一个常数的意义下给出匹配的下界。被略去的小规模层与叶子仅贡献 ,因此 。
在情形 3 中,只要子问题规模高于正则性的阈值,就应用正则性。深度 处的总代价项至多为 ,所以这些层的总和为 。一旦规模降到固定阈值以下,由于只涉及有限多个 的幂次规模,每个节点剩余子树的代价被一个常数所界定。这样的节点至多有 的常数倍个,它们的总代价为 。根代价项给出 ,从而证明了匹配的下界。
证明透视
正则性控制了什么
情形 3 的两个假设分别负责求和中的两个不同部分。间隙 使叶子的贡献 相对 可以忽略,答案才可以是 ,而不是两项之和。正则性控制的是另一部分:它说明每一代合并代价项之和至多是上一代的固定比例 ,所以逐层求和是一个收敛的几何级数,由首项主导。单靠间隙只是把根代价项与 比较,并不说明之后某一代的代价项会不会超过根,下面的振荡例子正说明这一点。匹配的下界是容易的一步,因为根代价项本身就是求和中的一项。
例题详解
例题 1.4.5
(较小的代价项)
对于 ,有 ,且 。由情形 1 得 。
例题 1.4.6
(对数代价项)
对于 ,有 且 。由情形 2 得 。这推广了配套单元中的精确逐层计算。
例题 1.4.7
(满足正则性的根主导工作量)
对于 ,有 ,且 。正则性条件在 时成立,所以由情形 3 得 。
常见错误
反例模式
缺乏正则性的大代价项
取 ,当 为偶数时令 ,当 为奇数时令 。它始终满足 ,但在 为奇数时,两个子节点的代价项之和为 ,远大于根代价项 。因此沿这些幂次, 不是 。可见情形 3 中的正则性条件不能简单地去掉。
常见错误
(把定理套用到取整递推式)
关于 的幂次的定理,并不会自动证明任意取整递推式也有相同的界。这需要另行作比较论证或递归树论证。
常见错误
(在情形 2 中使用负的对数指数)
情形 2 要求所述的固定 。若代入负指数,需要另作求和论证,下面的调和级数例子正说明这一点。
确定临界指数
指数 描述叶子的数目:。它是用来与非递归代价项相比较的参考尺度,不必是整数。例如,若 且 ,则 。代价项 多项式意义下小于 ,而 多项式意义下大于 。比较必须依据实际存在的正指数间隙,而不能仅仅观察几个输入处的数值差异。
渐近记号中隐含的常数对给定的递推是固定的。在情形 1 中,必须存在固定的 与常数 ,使得对每个充分大的允许规模都有 。在情形 3 中,同样必须存在固定的正间隙,以及严格小于一的正则性因子 。若某个因子随 趋于一,则它不满足带单一固定 的正则性条件。
例题 1.4.8
(非整数的临界指数)
对于二的幂次上的 ,有 。任取固定的 满足 ,则 ,由情形 1 得 。若把 四舍五入为二,并将二次界当作紧确结果,则是错误的。
审视逐层求和
精确展开使证明与任何具名情形相分离。在第 层,因子 计数节点个数,自变量 是每个节点的规模。基础项是 ,而不是再一次应用 ,除非递推明确这样定义。当 时,和式为空。这些约定避免重复计算叶子。
在代价项匹配的情形中,令 。子问题规模足够大的某一层的总代价与 成正比。靠近根的层 较大,靠近叶子的层 较小。把所有层相加就得到一个幂和。当 时,每个相关层贡献阶为 ,而层数提供一个对数因子。当 时,各层代价构成等差数列,其和提供两个对数因子。
条件 使得本定理所用的初等幂和估计一目了然。其他指数可能有不同的行为。例如,对 定义 。它比 小一个对数因子,但对任何固定的 都不是 。逐层恒等式给出 ,即对大的幂次为 。调和和的界可通过与 比较得到。这个例子说明了为什么对情形 1 而言,“小于 ”并不足够。
理解正则性
不等式 表示一个节点的各子节点的代价项之和至多是该节点代价项的某个固定比例。反复应用它,可使各层的总代价项呈几何递减,直到子问题规模降到阈值以下。有界的最终子树贡献另行处理;正则性不需要在基本规模本身成立。
在振荡反例中,问题不在于负的代价项或古怪的基本情形。每个代价项都为正且至少为 ,但沿着二的奇数幂次,子问题落在偶数指数上,具有大得多的三次代价项。这使得下一层超过根的代价,且倍数无界。仅有 的渐近下界并不比较相邻的层,因而不能确立根主导。
正则性检验应当用实际的函数和实际的自变量来写出。对于 且 ,计算 。比值是固定的 ,所以 可行。仅仅声称 “看起来很大”,遗漏了证明所需的条件。对于含有多项或振荡的函数,比值可能需要更细致的分析。
渐近界与精确代价
该定理给出渐近上界和下界,而不是精确常数,也不是小输入时的精确值。直接展开对于检查实现或某个拟议公式仍然有用。若 ,且在二的幂次上 ,则精确计算给出 。它与情形 3 一致,但仅凭该定理无法确定系数二或低阶项。
如果 仅作为算法每次调用的工作量的上界已知,那么求解上界递推本身并不能证明该算法的匹配下界。紧确的 断言需要对算法本身的适当下界,或者一个工作量非负的精确递推。同样,总工作量的递推并不自动界定峰值空间或并行经过时间;递归子问题可能以不同方式共享或重叠这些资源。
取整与适用性
许多程序把任意输入划分为规模为 和 的子问题。上面的证明假定每个节点的规模都恰为 ,且停止深度一致。取整往往可以控制,但所需的界取决于递推与基本情形。带线性代价项的平衡二路划分已在递归树单元中单独证明;那一具体论证并不是对每个取整递推的证明。
在调用本定理之前,应检查递归调用次数、除数、代价项、固定参数、基本情形和输入定义域。形如 的递推具有不同的形状。类似地,含有两个不等规模子问题的递推,若无比较证明,也不能硬套进相同的参数。符合定理的假设是求解的一部分,而不是点出某个情形之后可有可无的形式。
完整的情形选择计算
考虑三的幂次上的 ,基本代价为正常数。首先计算 。对于大的 ,,所以代价项为 。情形 2 适用,取 ,得 。对数底数之间的常数因子不影响结论。其中的项 保证了靠近基本情形处的代价项为正,但渐近分类取决于大的输入。
再考虑 。同样 ,但代价项在多项式意义下更大。计算正则性比值:。因此 可行,情形 3 给出 。同时写出指数比较和比值检验,可以避免仅凭一个假设就得出根主导的结论。
这两个例子还说明,为什么相同的分支因子会导致不同的总代价。在第一个例子中,节点的数目恰好抵消了每个节点幂次项的二次下降,使得每一层都留下一个对数代价项。在第二个例子中,每一层的代价是前一层的固定比例。该定理把这些逐层计算打包起来,但并没有免除识别正确代价项的需要。
对小规模尾部的检查
在情形 3 中,低于正则性阈值的第一层未必全由叶子构成。其节点在规模降至一之前可能还有若干代。然而阈值是固定的,低于它的 的幂次只有有限多个。因此,对于固定的递推,这些规模中最大的完整子树代价是一个常数。把该常数乘以边界处的节点个数,便得到所需的 尾部。这明确地计入了基本情形的工作量,同时没有在未作假设之处应用正则性。
总结
逐层恒等式把递推化为代价项之和。多项式意义下较小的代价项由叶子主导,匹配的幂次累积出一个对数和,多项式意义下较大且满足正则性的代价项由根主导。正则性是一个具有明确用途的假设。
练习
快速检查
(将该定理应用于 。)
先算 ,再与代价项的指数比较。
解答 · 答案
此处 ,且代价项在多项式意义下更小,所以 。
快速检查
(将它应用于 。)
先算 ,再判断代价项属于哪一种情形。
解答 · 答案
此处 ,,且代价项与 匹配,所以 。
快速检查
(检验 的正则性。)
计算 并与 比较。
解答 · 答案
有 ;正则性在 时成立,结果为 。
快速检查
(为什么叶子给出阶为 的下界?)
数一数叶子的个数及每个叶子的代价。
解答 · 答案
共有 个叶子,每个叶子的代价 为正。