cumt算法设计与分析期末考速通笔记（2）｜递归与分治

1 递归与分治的分析框架 #

递归必须有终止条件。分治将问题拆成规模更小的同类子问题，分别求解，再合并。

列递推式时确定三项：递归调用几次；每次规模多大；递归之外做多少工作。

2 汉诺塔 #

规则与递归 #

三根柱子；每次只移动一个盘子；任何柱子上都不能将大盘子压在小盘子上。目标是将全部盘子从起点移到终点。

移动(n,起点,辅助,终点)：
    如果n=1：移动一个盘子到终点；返回
    移动(n-1,起点,终点,辅助)
    将最大盘子从起点移到终点
    移动(n-1,辅助,起点,终点)

上面的n-1个盘子第一次移到辅助柱是给最大盘让路；最大盘到终点后，它们仍在辅助柱，必须再移到终点。

按移动次数计：T(n)=2T(n-1)+1，T(1)=1。

展开求解 #

令n-k=1，即k=n-1：

上下界与紧确阶 #

n≥1时：

故上界O(2ⁿ)，下界Ω(2ⁿ)，紧确阶Θ(2ⁿ)。实际程序运行时间与移动次数同阶。

3 二分查找 #

条件：数据有序。 每次比较中间元素，最多继续查找一半数据；不能把左右两边都递归查找。

按规模正好减半、n为2的整数次幂的模型：

令n/2ᵏ=1，得到k=log₂n，所以T(n)=1+log₂n，最坏时间为Θ(log n)。实际取整不改变数量级。

4 归并排序 #

手算过程 #

原数组：[8,3,6,2,7,1,5,4]

不断拆分：
[8,3,6,2]          [7,1,5,4]
[8,3] [6,2]       [7,1] [5,4]
[8][3][6][2]      [7][1][5][4]

逐层有序合并：
[3,8] [2,6]       [1,7] [4,5]
[2,3,6,8]         [1,4,5,7]
[1,2,3,4,5,6,7,8]

合并L=[3,8]、R=[2,6]时，每次取两组未取元素中较小的表头：

[] → [2] → [2,3] → [2,3,6] → [2,3,6,8]

“放到结果末尾”指接在已经排好的部分后面。结果从空开始增长，不是把小数放到最终数组的最后一个位置。

伪代码 #

归并排序(A)：
    如果长度(A)≤1：返回A
    将A分成左右两半
    L=归并排序(左半部分)
    R=归并排序(右半部分)
    返回合并(L,R)

合并(L,R)：
    i=0；j=0；结果=[]
    当i<长度(L)且j<长度(R)：
        如果L[i]≤R[j]：
            将L[i]追加到结果；i=i+1
        否则：
            将R[j]追加到结果；j=j+1
    将L尚未取出的元素依次追加到结果
    将R尚未取出的元素依次追加到结果
    返回结果

复杂度推导 #

两次规模n/2的递归，加上线性合并。简化令T(1)=1：

令k=log₂n，得T(n)=n+nlog₂n，因此为Θ(nlog n)。也可写：每层总工作量O(n)，合并约log₂n层。

易错点： 左右都要排序；合并不能直接拼接；一侧耗尽后补入另一侧剩余元素。

5 随机选择前k大 #

目标与划分 #

输出最大的k个元素，不要求内部有序。前k大指大小排名，不是原数组开头的k个位置。

在[7,2,9,4,6,1,8]中找前3大。
选4作基准：G=[7,9,6,8]，E=[4]，L=[2,1]。
G有4个，前3大必在G中，只递归G。

在[7,9,6,8]中选7作基准：
G=[9,8]，E=[7]，L=[6]。
G与E正好3个，返回[9,8,7]。

基准可以随机选取。不同基准影响步数，不改变正确选择规则的答案。

伪代码 #

约定0≤k≤长度(A)，重复元素也计入名额，数组加号表示拼接。

TopK(A,k)：
    如果k=0：返回[]
    如果k=长度(A)：返回A
    从A中等概率随机选择pivot
    G=大于pivot的元素
    E=等于pivot的元素
    L=小于pivot的元素
    如果k≤长度(G)：
        返回TopK(G,k)
    如果k≤长度(G)+长度(E)：
        返回G加上E中任取的k-长度(G)个元素
    返回G+E+TopK(L,k-长度(G)-长度(E))

若在[7,2,9,4,6,1,8]中选6为基准，G=[7,9,8]、E=[6]、L=[2,4,1]。找前5大时，先保留G和E的4个，再在L中找最大的1个，结果为[7,9,8,6,4]。

平均复杂度中的3/4 #

一次划分扫描当前数组，耗时O(m)。之后最多递归一组。等概率随机选基准时，递归组大小不超过两侧中较大者。

对8个互异元素，按从小到大排名分析：

最后一列平均值为44/8=5.5，小于8×3/4=6。分析排名不要求算法实际排序。

一般偶数m，两侧最大规模从m/2到m-1，每个值出现两次，平均为：

奇数m时也满足不超过3m/4。重复值不会扩大这个界。因此下一轮的期望规模至多为当前的3/4；不是每一轮实际都缩小到3/4。

期望时间与最坏时间 #

用c表示每个元素的固定工作量，各轮期望总工作量可被下式限制：

E表示期望。求和可令S为该级数，S-(3/4)S=cn，得到S=4cn。因此期望时间为O(n)。4cn是上界，不是每次恰好执行的次数。

最坏例：找最大值，但每轮都选当前最小值作基准，递归规模仅减少1：

考场结论： 随机选择前k大，平均O(n)，最坏O(n²)。不能用“每轮恰好减半”替代随机算法的平均分析。保证最坏线性的确定性选择尚待补充。