递推式描述的是特定成本模型下的特定算法;它并不仅仅因为程序是递归的就被确定下来。这里,数组索引、定宽算术运算和比较各花费常数时间。我们统计在给定输入上的工作量,当输入值可能改变控制流时,使用最坏情况界。
定义 2.4.1
(某成本模型下的递推式)
在指定成本模型下,某算法的递推式是一条等式,它把大小为 的输入上的成本 ,表示为该次调用自身所做的工作(不含递归调用),加上它所作递归调用的成本。它由代码推导而来,并且特定于该模型。
一个递归分支,然后是一个循环
对正整数 n,考虑 F(n):
F(n):
if n <= 1: return
for i = 1 to n: do one unit of work
F(floor(n/2))
定理 2.4.2
(折半递归的工作量与栈)
设 先执行 次迭代的循环,再对 调用自身,且 时立即返回。当 时,其总工作量满足 ,所以 ,而调用栈至多有 个栈帧。循环在递归调用之后执行时,结论相同。
证明
(不同循环长度构成的等比级数)
对于 2 的幂,各循环的长度为 n, n/2, n/4, ..., 2。它们的和小于 2n,而仅第一个循环就花费 n,因此 T(n)=Theta(n)。调用次数为 Theta(log n),但每次调用所做的工作各不相同。将 n 乘以调用次数,相当于把每个循环都当作最大的那个来计算。
这一论证并不依赖于 n 是 2 的幂:反复取下整只会减小循环长度,因此它们的和至多为 2n;而对于 n>1,第一个循环仍然给出线性下界。调用栈有 Theta(log n) 个栈帧;时间界并不会使空间界变成线性的。
反例模式
循环长度乘以调用次数会高估
一个诱人的界是把最大循环长度乘以调用次数,从而断言 。当 时,各循环的长度是 ,所以确切总数是 ; 共调用 11 次,其中 10 次执行循环。乘积 约高估 5 倍。对 ,确切总数是 ,所以 , 的断言不成立。正确的算法是把不同的循环长度相加,这是一个等比级数。
例题 2.4.3
(精确计算 F 在 n = 16、10 和 1 时的工作量)
当 时,各循环长度为 ,而 立即返回:总数为 ,共调用 5 次。当 时,参数依次为 :循环合计 ,介于 与 之间,共调用 4 次。当 时函数立即返回,工作量为 ,只有一次调用;不等式 只对 陈述。
概念视角组合
二进制数字给出精确代价
循环长度是 ,即把 的最后 个二进制数字去掉。价值 的数字,在 时对 贡献 ,因此对 的总和贡献 。逐位相加得 ,其中 是 的二进制展开中 的个数。参数为 的调用不执行循环,所以 时 。对 这是 ,对 是 ,对 是 。
两个分支不一定意味着平方时间
对长度为 n 的数组进行归并排序,会对两半各做一次调用,然后执行线性工作,把两个已排序的半部分归并到一个辅助数组中。对于 n=2^k,其递推式为
其中 c,d>0 表示理想化实现中的常数成本。在深度 j 处,有 2^j 个规模为 n/2^j 的子问题;它们的归并工作总量为 cn。共有 log_2 n 个内部层,另加 n 个常数成本的叶子。因此在这一模型下,T(n)=cn log_2 n+dn=Theta(n log n)。对于任意 n,按下整和上整分成两半仍保持同样的渐近界。实际的归并在不同输入上可能执行不同的比较次数,但复制所有元素的常规归并在每个内部节点上仍然做线性工作。
定理 2.4.4
(归并排序递推式的封闭形式)
对 , 与 的解是 。因此对常数 ,有 。
证明
(对 k 归纳)
当 时,公式给出 。设公式对 成立。则 。由于 ,这等于 ,即对 的公式。
对任意 (两半取下整与上整),同样的渐近界仍然成立;本节不证明这种情形。
例题 2.4.5
(c = d = 1、n = 8 时的归并排序递推式)
取 :,,,。公式给出 。按层计算:三层归并各花费 ,共 ;8 个叶节点各花费 ,共 。在 时同样检验得 ,在 时得 。
递归调用的次数和每次调用的工作量都必须计算在内。2T(n/2) 表示两个子调用的成本是相加的,而不是相乘。+cn 是递归调用之外的工作,在每个节点处计入一次。
重叠子问题:另一种树
定义 W(0)=0、W(1)=1,并且对 n>=2 有 W(n)=W(n-1)+W(n-2)。直接的递归实现会独立地计算这两项。例如,计算 W(5) 会调用 W(4) 和 W(3),而 W(4) 本身又会再次调用 W(3)。除非程序显式地存储结果,否则参数值相同的调用仍是各自独立的调用。
令 C(n) 表示调用次数(包括最初的调用)。则 C(0)=C(1)=1,并且
由于每个非基本情形的调用恰好产生两个子调用,这棵调用树是满二叉树。它有 W(n+1) 个叶子,因此 C(n)=2W(n+1)-1。叶子数公式可由同一递推式和相同的基本情形通过归纳法得到。因此,朴素算法会进行指数多次调用:对 n>=2,有 C(n)>=2C(n-2),而 C(n)<=2C(n-1)+1 给出指数上界。这些不等式足以说明指数增长,而无需精确的闭式表达。
定理 2.4.6
(朴素斐波那契(Fibonacci)递归的调用次数)
设 为调用次数,,且 时 。则对每个 ,,且 ,所以调用次数呈指数增长。
证明
(两个归纳证明)
关于公式:,。若对 与 成立,则 。关于下界:由于 不递减,。又 ,由归纳得 。
证明透视
两个归纳如何使用递推式
公式需要两个基底情形,因为 同时依赖 和 ;先验证 与 ,归纳步骤才能从 开始。递推式中的 与公式中的 互相抵消:。下界的关键一步,是把 与 比较,而不去解递推式。这需要 ,而它成立,是因为每个 使 。这个比较舍弃了一部分增长,所以只得出 ,是有效但较弱的下界。归纳每次前进两步,而 同时为两种奇偶性提供起点。
例题 2.4.7
(n = 5 与 n = 6 的调用次数,以及最小的情形)
由递推式得到,n=0,...,5 时的调用次数为 1, 1, 3, 5, 9, 15。自底向上的方法则先设定两个基本值,然后依次计算 W(2)=1、W(3)=2、W(4)=3、W(5)=5。对 n>=2,它执行 n-1 次加法;如果之后不需要重构,只需保留前两个值。在单位成本模型下,这需要 Theta(n) 时间和 Theta(1) 个存储值。精确整数会随 n 增长,因此任意精度下的位运算成本和以位计的存储量都比这一简化计数更大。
当 :,因为 ;自底向上需要 次加法。当 或 时只有一次调用,递归立即停止,自底向上不需任何加法。
记忆化是一种自顶向下的替代方法:存储每个已计算的 W(k),在后续请求时直接返回存储的值。需要一个单独的标记来区分“尚未计算”和计算结果为零的值。每个参数 0,...,n 至多计算一次,从而得到 O(n) 次单位成本操作和 O(n) 的存储(包括递归栈和表)。
常见错误
(把栈深度当作时间)
仍在执行的栈帧数是递归的深度,不是工作量。 至多约有 个栈帧,却需要 时间。把两者混淆,会得出 的时间,或 的栈空间。
常见错误
(把相同参数当作同一次调用)
在朴素递归中, 在 之下被调用一次,在 之下又被调用一次。除非存储结果,否则每次出现都是独立的调用,所以 共作 次调用,而不是 这 6 个不同参数。只数不同参数描述的是记忆化,而不是朴素程序。
已解练习:要推导,不要猜测
快速检查
(对正整数 n,以下代码递归地把 n 减半,并在返回后执行一个 n 次迭代的循环。它的时间上界及辅助栈上界是什么?)
G(n):
if n <= 1: return
G(floor(n/2))
for i = 1 to n: do one unit of work
把循环规模与 的比较一下。
解答 · 答案
递归调用和循环的顺序改变了,但循环规模仍为 n, floor(n/2), floor(n/4), ...。它们的和为 Theta(n)。在最大深度处有 Theta(log n) 个活跃调用,因此栈使用 Theta(log n) 个栈帧。顺序影响的是工作在何时完成,对于有状态的代码还可能影响输出,但在所述假设下,它不会改变这一操作计数。
快速检查
(朴素递归计算 要作多少次调用?)
用 及 以内的已知数值。
解答 · 答案
,与 一致。
快速检查
(某函数对 作一次递归调用,其余只做常数工作。它的时间与栈上界是什么?)
先写出递推式。
解答 · 答案
递推式是 ,基本情形为常数,所以 。递归深度为 ,所以栈使用 个栈帧,与折半函数 不同。