笔记: 算法分析 04

上一节中, 我们已经在排序问题里见过两种典型的递归结构: 归并排序把数组均匀地分成两半, 快速排序则根据枢轴的位置产生两个大小不定的子问题. 归并排序的运行时间满足

而快速排序在极端不平衡的划分下会退化到

与此同时, 比较排序的决策树模型告诉我们: 对 个互异元素, 必须区分 种可能的排列, 因此任意比较排序在最坏情况下都需要

次比较. 归并排序达到了这个渐进下界.

这些结论在上一节已经讨论过, 这里不再重复证明. 真正值得抽象出来的问题是:

为什么同样是 “递归地把问题切开” , 有的算法能得到 , 有的仍然是 ; 而有时, 仅仅少做一次递归调用, 就足以改变整个算法的增长阶?

这正是分治法要回答的问题.

1. 从一个排序技巧到一种设计方法

归并排序最重要的意义并不只在于 “会排序” , 而在于它展示了一种可以反复迁移到其他问题中的结构.

“分成更小的问题” 本身并不会自动带来更快的算法. 分治算法的效率通常由三个因素共同决定:

• 每次产生多少个递归子问题;
• 每个子问题缩小到什么规模;
• 分解与合并还需要付出多少非递归工作.

因此, 学习分治法不能只关注 “怎么切” , 还要同时回答两个问题:

1. 为什么这些子问题足以覆盖原问题? ——这是正确性问题;
2. 递归结构最终会产生多少工作量? ——这是复杂度问题.

下面先用最大子数组问题完整地走一遍这个过程.

2. 最大子数组: 怎样把 “跨越边界” 的情况找出来?

2.1 从股票交易到连续子数组

假设已经知道一只股票未来每天收盘后的价格

只能买入一次, 并且必须在买入之后卖出一次. 若在第 天后买入、第 天后卖出, 其中 , 收益为

直觉上, 人们很容易想到 “最低点买、最高点卖” . 问题在于, 最低价可能出现在最高价之后. 更进一步, 即使分别固定全局最低价或全局最高价, 也不一定得到最优交易.

例如价格序列

中, 最优交易是在价格 时买入、价格 时卖出, 收益为 . 这里的买入价不是全局最低价 , 卖出价也不是全局最高价 .

真正有用的变换, 是不再观察 “价格” , 而观察相邻两天的 “价格变化” . 定义

于是

原来的股票交易问题因此变成: 在数组 中, 寻找一个连续且非空的区间, 使区间内元素之和最大.

“非空” 这个约定很重要. 若数组中所有元素都为负数, 答案应当是其中最大的那个负数, 而不是和为 的空区间.

2.2 先看最直接的方法

一共有 个非空连续子数组. 若枚举所有左右端点, 并利用前缀和在常数时间内得到每个区间的和, 就能得到一个 的算法.

这已经比 “每个区间重新求和” 更好, 但仍然没有利用问题自身的结构.

分治法提出了另一个问题:

如果已经知道左半段和右半段各自的最大子数组, 还缺少什么信息, 才能得到整个区间的最大子数组?

2.3 三种位置关系

考虑当前区间 , 令中点

任意一个连续子数组, 相对于这个中点只有三种可能:

1. 完全位于左半部分 ;
2. 完全位于右半部分 ;
3. 同时包含 与 , 即跨越中点.

前两种情况正好是两个规模更小的同类问题, 因此可以递归求解. 于是问题的关键落在第三种情况: 怎样在线性时间内找到最优的跨中点子数组?

一个跨越中点的连续子数组必然可以唯一地拆成两段:

• 左边是一段以 结尾的后缀;
• 右边是一段以 开始的前缀.

因此令

那么跨越中点的最大子数组和恰好就是

计算 时从 向左扫描一次, 计算 时从 向右扫描一次, 总工作量为

一个容易忽略的实现细节是: 记录左右最优值时应初始化为负无穷, 而不是 . 否则在全负数组中, 算法可能错误地把 “什么都不选” 当成更优答案.

MAX-CROSSING-SUBARRAY(A, l, m, r):
    left_best = -∞
    s = 0
    for i = m downto l:
        s = s + A[i]
        if s > left_best:
            left_best = s
            left = i

    right_best = -∞
    s = 0
    for j = m + 1 to r:
        s = s + A[j]
        if s > right_best:
            right_best = s
            right = j

    return (left, right, left_best + right_best)

2.4 完整的分治算法

MAXIMUM-SUBARRAY(A, l, r):
    if l == r:
        return (l, r, A[l])

    m = floor((l + r) / 2)

    left  = MAXIMUM-SUBARRAY(A, l, m)
    right = MAXIMUM-SUBARRAY(A, m + 1, r)
    cross = MAX-CROSSING-SUBARRAY(A, l, m, r)

    return left, right, cross 中总和最大的一个

这里的 “分解—解决—合并” 已经非常清楚:

• 分解: 在中点把区间分成左右两半;
• 解决: 递归寻找左右两边的最大子数组;
• 合并: 额外求出跨越中点的最优解, 再从三者中取最大者.

更重要的是, 三种情况不是一种经验性的分类, 而是一个穷尽且互斥的分类, 这正是正确性证明的核心.

2.5 为什么这里自然地使用强归纳法?

普通数学归纳法在证明 时, 通常只假设 ; 强归纳法则可以假设

全部成立.

普通归纳法与强归纳法在逻辑力量上是等价的, 但强归纳法更贴近递归算法的结构: 规模为 的问题调用的子问题只需要保证 “规模更小” , 未必恰好是 .

2.6 最大子数组分治算法的运行时间

设 为处理长度为 的区间所需时间. 暂时假设 是 的幂, 则

而对 ,

两个递归调用来自左右两半, 则来自跨中点扫描及常数次比较.

这个递推式和归并排序完全相同. 若把非递归部分暂写成 , 连续展开 层,

当 时, 子问题规模降到 , 于是

因此分治算法把朴素的 改进到了 .

但这还不是最大子数组问题的最优复杂度: 它存在 的算法. 本节的目的不是追求这个问题本身的最快算法, 而是借它看清分治设计中 “递归求两侧, 再处理跨边界情况” 的一般结构.

3. 大整数乘法: 分治为什么可能毫无帮助?

最大子数组的例子容易让人产生一种误解: 只要把问题不断对半分, 复杂度就会下降.

大整数乘法正好说明这种想法为什么不对.

设 都是 位二进制整数. 传统竖式乘法需要逐位处理约 对数位, 因此时间复杂度为 .

为了使用分治, 先假设 是偶数, 并写成

其中 都只有约 位. 直接展开得到

如果照着公式计算, 我们必须递归计算四个半规模乘法:

加法与按 的幂移位都只需要处理 位, 因此

连续展开可以看到, 递归到底层后共有

个常数规模乘法, 于是

也就是说, 我们设计出了一个结构完全不同的递归算法, 却没有得到任何渐进改进.

问题出在哪里? 不是 “子问题不够小” , 而是子问题太多.

3.1 从四次乘法降到三次

注意真正麻烦的是交叉项

我们不必分别计算这两个乘积. 令

展开 ,

所以

于是四个递归乘法减少为三个:

这一次改变看似很小——每层只少了一次递归乘法——但它会在每一层递归中重复发生. 展开到最底层时, 叶子数从

下降为

而

所以

实际实现时也没有必要一直递归到单个二进制位. 当整数已经小到机器可以高效直接相乘时, 通常切换到普通乘法更实际; 这不会改变上面的渐进分析.

4. 矩阵乘法: 同一种思想再出现一次

设 是两个 矩阵, 把它们分别按行列各切成两半:

其中每个子块都是约 的矩阵.

按普通的分块乘法,

一共需要 次半规模矩阵乘法, 而矩阵加法与合并需要 时间, 因此

它的解仍然是

与三重循环的普通矩阵乘法处在同一个渐进阶.

这和刚才的大整数乘法完全一样: “做了分治” 不等于 “变快了” .

4.1 Strassen 的关键: 用加减法换掉一次乘法

Strassen 算法的突破不是把矩阵切得更小, 而是发现: 四个结果分块并不一定需要上面那 个子矩阵乘法. 通过重新组合, 可以只做 次乘法.

为了看清这不是一句魔法式的 “存在七次乘法” , 记

可以计算下面七个乘积:

然后恢复乘积 的四个分块:

逐项展开即可验证这些式子等价于普通分块乘法. 这里增加的是常数次矩阵加减法, 仍只需要 时间; 真正昂贵的递归矩阵乘法则从 次减少到了 次. 因此

递归到底层时, 常数规模乘法的数量约为

其中

所以

大整数乘法中的 “ 变 “ 与 Strassen 中的 “ 变 “ 揭示的是同一个设计思想:

如果递归调用是算法中最昂贵的部分, 那么宁可增加一些便宜的线性组合, 也可能值得换掉一次递归调用.

5. 递推式: 把递归程序压缩成一个数学对象

到这里, 我们已经连续遇到四个递推式:

这不是巧合. 递推式正是描述分治算法运行时间最自然的语言.

这个形式很常见, 但并不是所有分治算法都必须长成这样. 快速排序可能得到大小不等的子问题, 某些算法也可能只产生一个子问题, 甚至递归参数还会带常数偏移. 真正重要的是: 先从算法结构正确建立递推式, 再讨论怎样求它的渐进解.

本节首先学习最基本也最严谨的方法: 代入法.

6. 代入法: 猜测不是答案, 归纳才是证明

“代入法” 这个名字来自归纳步骤: 我们把对较小规模的猜测代入原递推式.

这里最重要的一点是: 猜出 并不等于证明了 . 真正要证明的是存在一个固定常数 , 使

对充分大的 成立.

6.1 一个标准例子

考虑

为了先把技术细节放在一边, 假设 是 的幂. 根据归并排序和最大子数组的经验, 猜测

也就是说, 我们要证明: 存在 , 使

同理, 如果递推式中的线性项也有相应的正下界, 就可以选择合适的常数证明

上下界合在一起, 才得到

6.2 基例为什么不能草率写成 ?

递归的基础情形只需要满足 , 并不要求恰好等于 . 为了看清一个常见的技术问题, 暂取 . 若我们的归纳命题是

那么代入 得到

显然不成立.

这并不说明 的猜测有问题. 大 的定义本来就只要求不等式在 “充分大的 “ 上成立, 因此归纳证明完全可以从某个 开始.

例如把 作为归纳证明的基例, 并把 取得足够大即可. 这里需要区分:

• 递推式本身的基础情形, 例如算法在 时停止;
• 归纳证明的基础情形, 它可以从更大的常数规模开始.

二者不必相同.

6.3 递推式里的 不能当作一个具体的

如果写成

其中的 不是某个可以随意替换为 的 “数” .

更严谨地说, 设非递归工作为 . 由

可知存在常数 与 , 使充分大的 满足

因此:

• 证明上界时使用

• 证明下界时使用

最终分别得到 与 , 才能合成 .

7. 真实递推式通常没有那么整齐

7.1 不是 的幂怎么办?

如果把长度为奇数的数组分成两半, 严格地说, 两个子问题的规模应当是

例如更精确的递推式可能是

在渐进分析中, 经常有两种处理办法.

第一种是保留取整符号, 在归纳证明中使用

之类的不等式.

第二种是在算法允许的情况下, 把输入补齐到不超过原规模常数倍的方便大小, 例如补到最近的 的幂. 对常见的单调运行时间函数, 这种常数倍放大不会改变我们关心的渐进阶.

这里不能把 “忽略取整” 理解成任意删除数学细节; 它成立的原因, 是这些细节最终只造成可控制的常数级偏差.

7.2 两个子问题不一样大

分治也不要求所有子问题等大. 考虑

直觉上, 每一轮仍把全部元素分到两个较小子问题中, 因此猜测

假设对更小规模有

则

整理得到

令

只要选择

就有