11.3 递推方程的其他解法
本章目录 · 1 节
本章导读
【换元法】先将递推变量或未知函数作变换,化为较易求解的方程,求解后再还原。必须记录换元的适用范围;在 上推出的精确公式,不能不加说明直接断言对任意n仍精确。
【例11.3.1】二分归并排序。对A[p..r],若p≥r则结束;否则置 ,递归排序A[p..q]和A[q+1..r],最后调用Merge将两段归并。最后一步是Merge而不是再调用有四个区间参数的Mergesort。
归并时用两个指针比较两段尚未取出的首元素,将较小者追加到输出,直到一段耗尽,再追加另一段余项。两个非空有序段共n个元素,至多进行n−1次关键字比较。n=2ᵏ时,最坏比较次数满足
置 ,则 。特解试 ,得A=B=1,齐次通解为c2ᵏ,由初值得c=−1。还原得到
也可迭代:展开j次后
取j=k,W(1)=0即得同一结果。代入n=1符合初值;将公式代回 也恢复原式,这构成归纳验证。对一般n,使用取整后的子问题递推可得 ,而以上精确式只针对2的幂。(例完)
【例11.3.2】错位排列。Dₙ表示n个不同元素中没有元素位于原位置的排列数。可补上 。固定元素1所占的非原位置j,有n−1种选择;若j回到位置1,余下n−2个元素为错排;否则通过删除元素1并将有关位置重新标记,与n−1个元素的错排一一对应。因此
令 ,则 ,E₂=1,故 。于是原二阶变系数递推化为一阶式 。除以n!并迭代:
这与包含排斥原理所得结果相同。不能把“删去第一位后自然就是错排”当成证明;第二类还需要对应的重标记。(例完)
【全部历史递推与快速排序】快速排序先选基准,将比它小、大的元素分到两侧,再递归排序两侧。若所有元素互异,基准最终位于第k位,两侧规模分别为k−1、n−k。随机等可能选择基准,或输入是等可能的随机排列时,k在1到n之间均匀分布。固定首元素作为基准并不意味着任意输入都自动具有这个平均情形。
为避免原伪代码的严格比较搜索越界及划分接口混用,给出“基准保留首位”的完整双指针版本,区间为闭区间A[p..r]:置x=A[p]、i=p+1、j=r。反复执行:当i≤j且A[j]>x时令j减1;当i≤j且A[i]<x时令i加1;若i≥j则退出,否则交换A[i]和A[j]并令i加1、j减1。退出后交换A[p]与A[j],返回q=j。快速排序仅在p<r时调用这个过程,再递归处理A[p..q−1]、A[q+1..r],不在调用者中重复交换基准。短路判断保证不访问越界位置,重复值也不会使交换后的指针停滞。
原例数组为27,99,0,8,13,64,86,16,7,10,88,25,90。先后交换99与25、64与10、86与7,得到27,25,0,8,13,10,7,16,86,64,88,99,90;最终交换27与16,得16,25,0,8,13,10,7,27,86,64,88,99,90,基准的一基下标q=8。划分并没有把左右各段内部排序。
【例11.3.3】平均复杂度。用dₙ表示一次划分的平均代价,则
这依赖所有较早项,称为全部历史递推。若只知 ,不能直接将它改写成一个固定cn再把大O项当等式相减。可用归纳比较:选c使 ,以 、U₀=U₁=0作上界。对n≥3,将nUₙ与(n−1)Uₙ₋₁相减,得
除以n(n+1)并求和,得 ,故 。这里n=2应单独使用U₂=2c,不能套用不适用n=1的原递推。
若要精确比较次数,可采用“一次划分让其余n−1个关键字各与基准比较一次”的明确模型,此时 ,而不是上述双指针实现的逐条指令计数。差消可得 ,进而
调和和为 ,故该模型的平均比较次数为 。若每次都选到极端基准,最坏情况仍为 。
[[fig:ls-c11-1131|图11.3.1 调和和的积分上界;每个区间[j−1,j]上的矩形高度为1/j,矩形在曲线1/x下方]]
例如 。积分的变量应为x,上下限与右端点矩形一致,不能把图中的n+1误写成n+2。(例完)
【递归树】对归并递推,初始单结点权为W(n),展开后根权n−1,两个叶权W(n/2);继续展开直到子问题规模为1。第j层有2ʲ个内部结点,各权n/2ʲ−1,故该层和为n−2ʲ。j=0到k−1共k层内部结点,另有深度k的叶层,叶权为W(1)=0。不能把“规模1”写成“初值1”。各次展开保持全树权和不变,因此
【一般分治递推】设a≥1、b≥2是整数,n=bᵏ,初值T(1)=1,递推 。b必须大于1,否则子问题规模不会递减。展开得到
若d(n)=c>0,a>1时 ;a=1时T(n)=1+ck,量级为Θ(log n)。
若d(n)=cn,c>0,则 。于是a<b时为Θ(n),a=b时为Θ(n log n),a>b时为 。将d仅写成O(n)通常只能保证对应上界,不能在缺少正下界时直接声称Θ(n)。归并d(n)=n−1在n≥2为Θ(n),故可得到Θ(n log n)。
【例11.3.4】快速幂与斐波那契矩阵。n=2ᵏ≥1时,Power(a,n)在n=1返回a,否则先保存x=Power(a,n/2),再返回x·x。必须保存递归结果,且只递归一次;若分别算两次半幂,就失去这一复杂度优势。乘法次数M(1)=0、M(n)=M(n/2)+1,故M(n)=log₂n。
令 ,Q为二阶矩阵,则
n=1成立;右乘Q使矩阵每个位置按斐波那契递推更新,故归纳成立。直接求Qⁿ并读取右上角即可得到Fₙ。也可求Qⁿ⁻¹读左上角,但即使n是2的幂,n−1一般也不是,不能直接调用只支持2的幂的原版本。
支持任意非负整数指数的版本为:n=0返回单位元I,n=1返回a;否则递归求x=Power(a,⌊n/2⌋),置y=x·x,n为偶数时返回y,奇数时返回y·a。对矩阵单位元为单位矩阵。这样只需O(log n)次固定阶矩阵乘法,每次普通2×2矩阵乘法为8次标量乘法。与逐项递推需要O(n)次加法相比,算术运算次数减少;但Fₙ的位数随n增长,不能把大整数乘法和加法都误算成固定耗时,也不能据此断言所有输入规模下实际速度必然相同。(例完)
