动机
用 n 除以 b 写出的递推式常常掩盖了输入规模是整数这一事实。把上取整换成精确分数,可能改变递归停止的位置,尤其是在最小的输入处。证明应当从实际反复取整后的规模出发,并且既要计入内部工作,也要计入最后的叶子。
三种常见的增长情形来自各层之上的几何级数求和。当代价项含有对数时,等号情形会更微妙:多出一个对数因子并不总是正确答案,而倒数对数会产生另一个边界。
下面的整数规模分析处理的是各分支一致、固定分支数的递推,并明确要求基础值与代价项的界为正。分支不等、任意依赖数据的分支,以及负代价之间的抵消,都不是这些假设的推论。
定义
定义 3.2.1
(一致的取整递推及其代价项)
固定整数 、 和实数指数 。设正的基础值为 。对整数 ,考虑
其中 c、C 是固定的正常数。这 a 次递归调用的输入规模都是上式所示的取整后规模。这是一个数学意义上的工作量递推;常数和界与 n 无关。
记 。上取整递归在规模为一时停止,因此规模为一的调用是基础情形,而不是又一次递归调用。空输入的工作量可以另行定义,且从不进入这个正规模的递推。
定义 3.2.2
(下取整版本及其基础情形约定)
对于下取整版本,对每个满足 的整数 n 取固定的正有界基础值,并且仅对 应用 。此时 c 与 C 约束的是该递归范围内的代价项。这一基础情形约定避免了出现未定义的规模为零的调用。
所有渐近常数可以依赖于 a、b、d、c、C 以及有限个基础值,但不依赖于 n。算术运算代价与位运算代价的区别必须已经计入 g 之中;递推式本身并不声明长整数算术是常数代价。
定理/命题
定理 3.2.3
(上取整递推:三种几何情形)
对于上取整递推,
递归恰有 层内部展开,以及 个叶子。这些公式也涵盖链状情形,即 a 等于一且 d 为零,此时工作量是对数级而非常数级。
定理 3.2.4
(下取整递推具有相同的增长阶)
在所述的下取整基础情形约定和正的代价项界之下,同样的三种渐近情形成立。对至少为一的 n,其深度为 ,并且每个叶子的规模从一到 b 减一。
不需要对某个未指定的未知工作量函数假设单调性:每一层上实际取整后的子问题规模可以被直接估计。
定理 3.2.5
(临界对数代价项还有三个阈值)
在恰为幂的输入 上,改为假设 ,使用同样的正基础值,并且
在递归的幂输入处成立,其中 r 为实数。那么当 L 趋于无穷时,
基础情形和有限个较小的幂另行处理,因此不会对零取对数。该命题仅限于恰为幂的输入;其证明并不会不加说明地变成一个取整后分支混杂的定理。
证明思路或证明
求出每一层取整后的规模
证明
(取整后的规模与逐层求和)
对正整数 b 和实数 x,反复相除满足
整数 j 不小于左边的式子,当且仅当 ,也就等价于 ,由此证明该恒等式。归纳可知第 j 层的规模为 。
第一个规模为一的层满足 ,从而 。在该层之前,比值大于一,所以
该层恰有 个结点,因为每个内部结点都发起 a 次调用,且规模都相同。它们合起来的代价项,其上下界是 的固定正倍数。这些不等式在 d 为零时仍然有效。
因此,把递推展开到实际的叶子,得到
两边都包含正的基础代价。当 n 为一时,求和为空,叶子项就是基础值;此处无需分配任何内部代价项。
计算求和并保留叶子
证明
(几何情形与叶子)
令 。若 q 小于一,则其几何级数的部分和有统一的上界,并且在 n 大于一时至少为一。另外 ,并且因为 L 与 相差不到一,所以 。因此,根结点规模的代价项决定了答案。
若 q 等于一,则每个内部层的贡献都是 阶。这样的层有 L 个,而叶子的贡献是 阶。总和为 ,得到所述的边界形式。当 a 为一且 d 为零时,每层只有一个结点,各自带有正的常数代价,所以对数是必不可少的。
若 q 大于一,则几何级数的和对正的 L 是 阶。其代价项的贡献为 阶,而叶子项恰好是同一阶。因此叶子规模的增长占主导。在这个情形下,叶子并不是低阶的修正项,而与内部各层同阶。
证明透视
竞争发生在分支与缩小之间,而不只是根结点的代价项
在每一层,分支使结点数乘以 a,而规模缩小使每个多项式代价项除以 b 的 d 次方。它们的比值决定了相继各层是缩小、保持相当还是增长。正的基础代价使最后一层始终可见,即使后来对数型代价项迅速衰减也是如此。
下取整的规模同样允许直接比较
证明
(下取整的规模与同样的比较)
下取整对应的恒等式是 ,因为在整数除法下,定义下取整的整数区间具有相同的商端点。于是 。
第一个基础层的规模小于 b 且至少为一,从而 。在每个内部层,,所以
下界的比较来自:当 x 至少为二时,x 减一不小于 x 除以二。因此每一层的代价项都与之前一样有固定倍数的比较。有限个正的基础值有正的最小值与有限的最大值,所以全部叶子合起来的代价仍是 阶。再次使用几何级数的各种情形,就证明了下取整定理,而无需借助未经证明的单调性假设去比较 T 在不同输入处的值。
上界递推不自动给出双向运行时间估计
正的局部工作下界才保证各个 结论的下界。程序若只给出局部工作上界,展开树只能证明上界,不能创造实际不存在的工作。例如单个向上取整减半调用,局部工作为一时总量为对数级,局部工作为输入大小时总量为线性级;两种局部工作都满足同一个线性上界。
实际子调用数也须核实。乘法程序发现零操作数后可能省略某个分支;三分支完整树仍给出上界,但匹配的下界需要一族不会触发捷径的输入。分别最大化局部工作和各个孩子,也不保证同一输入能同时达到所有最大值。
所以应先说明递推是精确工作恒等式、最坏情形上界,还是具有可实现下界的双向模型。本篇定理针对已声明的正恒等式;工作更少的程序可继承上界,却须另证下界才能声称 。优化某些执行不会与完整树上界矛盾。
临界对数化为深度上的幂和
证明
(临界对数化为幂和)
对于恰为 的 n,第 j 层的子问题规模为 。在临界情形 下,该层合起来的代价项为
阶。固定 b 与固定 r 使对数底的因子成为常数。令 h 等于 L 减 j 并求和:
当 r 大于负一时,由初等的积分比较,或者由二进分块再加上和式的后一半,得到 阶。这包括该范围内的负 r:后一半中的每一项都与 相差一个固定因子,由此得到下界;对递减幂函数积分则得到上界。对非负的 r,使用相应的递增函数比较。
当 r 为负一时,和式是调和级数,介于 与 之间。当 r 小于负一时,该正项级数以一加上其收敛的广义积分为上界,并以其首项为下界。于是保留下来的叶子项具有同样的归一化常数阶。代入 L 与 log n 成比例,就证明了全部三个阈值。
这些积分比较针对的是正的标量级数;它们并不假设原来未知的 T 是单调的。这一区分使得精确的整数递归在前面各定理中始终保持明确。
例题详解
例题 3.2.6
(上取整的边界会改变精确答案,却不改变其阶)
取 以及 。当 n 为八时,深度为三,有八个叶子和七个内部结点,所以 T 为十五。当 n 为九时,深度为四,有十六个叶子和十五个内部结点,所以 T 为三十一。
该递推处于叶子占主导的情形,其中 p 为一而 d 为零,因此两个答案都符合线性的渐近增长。如果用精确的一半来代替取整后的规模,就会错过这一精确的跳变及其正确的停止层。
例题 3.2.7
(根占主导的递推仍可能有若干完整的层)
设 且 。当 n 为七时,第一个子规模为三,其子规模为一。总工作量是根的代价项七,加上下一层的代价项 ,再加上四个单位叶子,共十七。
这里 ,所以总的阶是线性的。根占主导描述的是求和后的量级,并不是断言所有非根的工作量字面上都消失。
例题 3.2.8
(一个临界对数会在总量中产生两个对数)
在 2 的幂上,取基础值为一,并令 。把各层之和除以 n,得到一加上整数一到 L 的和。当 n 为八时,L 为三,T 为 。
定理给出 。若代价项改为 n,则归一化的和将是一加 L。代价项中的对数改变了每一层的贡献,在套用临界情形之前必须把它计入。
概念视角分析
递归树是以尺度为下标的求和
精确的取整确定了哪些尺度真正出现。多项式代价项在这些尺度之间形成几何级数,而临界对数代价项则对剩余深度形成幂和。证明是一个受控的有限和,并单独计入边界,而不是把分数输入规模代入一个未定义的函数。
常见错误
反例模式
上取整递推需要正规模的基础情形
如果只把规模为零声明为基础情形,并对每个正的 n 都递归地使用 ,那么规模为一的调用会调用自身。其方程为 ,没有有限的非负工作量解。在应用任何主定理估计之前,必须先指明取整与终止的假设。
常见错误
(只计内部结点的代价项)
只把内部结点的代价项加起来就停下,会漏掉叶子,而每个叶子都要付出一个基础值。取 与 ,并令 。内部代价项共计 ,但 ;当 时是 ,而不是 。应像上面的逐层求和那样,明确计入 个叶子。
常见错误
(对数型代价项仍沿用边界形式)
在临界情形 而代价项含有对数时,容易误以为仍是 的形式,或只需多乘一个对数。在 2 的幂上取 与 。逐层求和给出 ,所以 无界: 时为 , 时为 。正确的阶是 ,这正是 时的临界对数定理。
不要在没有证明单调性的情况下使用单调性夹逼,也不要把恰为幂的对数定理转用到任意不等分的子问题上。负的开销抵消、依赖数据的分支以及大整数算术,都需要各自的模型和界。
总结
反复的整数除法给出精确的上取整、下取整规模以及停止深度。逐层比较把多项式代价项化为带有正叶子项的几何级数,而临界对数则化为深度上的幂和。这就在不隐藏取整、基础情形或代价模型的前提下,证明了精确的渐近情形。
练习
快速检查
(对 (基础值为规模一时取正)进行分类。说明为什么除非代价项本来就是按位度量的,否则该定理本身并不能确定某个实现的位运算代价。)
比较三与二的一次方。
解答 · 分支产生乘法指数
这里 p 为 ,并且 ,所以界为 。这是关于所声明的工作量函数的结论。如果 g 计的是长整数上的字操作,仍然需要另行做位代价分析;递推定理不会把这些操作变成单位位工作量。
快速检查
(在 2 的幂上,求一个有两次半规模调用、代价项为 的递推的阶。在规模为一处保持正的基础值。)
归一化的深度和是调和级数。
解答 · 倒数对数给出 log-log 因子
当 n 等于 时,每一层的贡献是 n 除以其剩余深度,至多差一个固定的对数底因子。因此当 L 趋于无穷时,T 除以 n 的阶为 。结果是 ,有限个最小的幂以及正的基础值另行处理。
快速检查
(对 、 的下取整递推,规模一与二处的基础值均为一,代价项为 ,精确计算 。)
第一个取整后的子规模已经是基础规模。
解答 · 一次展开得到十
下取整除法把八变为二。因此 。深度公式给出 ,与之一致。若使用上取整,则八会变为三并需再展开一次,得到另一个不同的精确递推,尽管对应的大输入阶仍是线性的。