Microsoft Word - 1P.doc

机 械 工 业 出 版 社 华 章 公 司 迷 你 书 算 法 之 道 作 者 : 邹 恒 明 ( 上 海 交 通 大 学 ) ISBN:978-7-111-9494-8 定 价 :39. 出 版 社 : 机 械 工 业 出 版 社

第 3 章 分 治 与 递 归 你 站 在 桥 上 看 风 景, 看 风 景 人 在 楼 上 看 你, 明 月 装 饰 了 你 的 窗 子, 你 装 饰 了 别 人 的 梦 卞 之 琳 上 面 这 首 诗 包 含 的 是 一 个 递 归 概 念, 而 图 3-1 则 明 显 地 展 示 了 递 归 如 果 细 心 些, 你 还 会 发 现, 生 活 中 到 处 都 是 递 归! 图 3-1 递 归 无 处 不 在 : 递 归 的 蒙 娜 丽 莎 例 如, 很 多 人 恐 怕 都 见 过 一 个 这 样 的 称 球 游 戏 : 给 定 个 球, 其 中 1 个 球 为 次 品 次 品 从 外 表 上 看 与 正 常 球 一 样, 但 重 量 有 区 别 它 可 能 比 正 常 球 重, 也 可 能 比 正 常 球 轻 现 在 给 你 一 个 天 平, 我 们 的 问 题 是, 需 要 称 几 次 才 能 将 次 品 甄 别 出 来? 这 个 问 题 的 解 答 思 路 十 分 简 单 : 就 是 将 次 品 所 在 的 范 围 不 断 缩 小, 直 到 只 有 1 个 球 为 止 例 如, 先 将 所 有 的 球 分 解 为 两 个 相 等 的 部 分 ( 如 果 为 奇 数, 则 无 法 分 解 为 相 等 的 部 分, 但 本 思 路 仍 然 适 用 ), 将 其 置 于 天 平 的 两 端, 如 图 3- 所 示 此 时 必 然 一 端 重 一 端 轻 问 题 是 我 们 并 不 知 道 次 品 是 重 还 是 轻 因 此 需 要 分 别 对 每 部 分 的 / 个 球 再 进 行 一 次 上 述 这 样 的 测 试 如 果 平 衡, 则 这 部 分 的 / 个 球 均 为 正 品, 即 次 品 在 另 外 的 / 个 球 里 否 则, 次 品 就 在 这 / 个 球 里 这 样 我 们 就 将 寻 找 次 品 的 范 围 缩 小 了 一 半

6 第 一 篇 算 法 基 础 篇 图 3- 用 天 平 来 称 球 并 辨 别 次 品 用 到 了 递 归 策 略 我 们 可 以 按 照 这 个 方 法 不 断 缩 小 次 品 范 围, 直 到 解 决 为 止 ( 次 品 范 围 只 有 1 个 球 的 时 候 ) 而 这 种 将 次 品 范 围 不 断 缩 小, 但 解 题 方 法 维 持 不 变 的 方 法 就 是 递 归 当 然, 本 章 对 递 归 进 行 讨 论 并 不 是 因 为 我 们 要 称 球, 或 者 生 活 中 到 处 都 存 在 递 归, 而 是 因 为 在 算 法 的 设 计 与 分 析 中, 递 归 是 一 个 普 遍 且 难 以 回 避 的 解 题 方 法 更 有 意 思 的 是, 递 归 又 常 常 与 算 法 里 面 的 另 一 个 重 要 概 念 分 治 ( 分 而 治 之 ) 紧 密 联 系 事 实 上, 递 归 在 很 多 时 候 就 是 因 为 分 治 策 略 的 使 用 才 出 现 的, 可 以 说, 没 有 递 归, 就 没 有 分 治 分 析 一 个 分 治 策 略 的 优 劣 经 常 牵 涉 对 递 归 表 达 式 的 分 析 例 如, 我 们 前 面 的 称 球 游 戏 在 使 用 递 归 的 同 时 也 使 用 了 分 治, 即 将 规 模 较 大 的 问 题 ( 在 个 球 里 面 寻 找 次 品 ) 化 解 为 同 类 型 的 规 模 较 小 的 问 题 ( 在 / 个 球 里 面 寻 找 次 品 ) 本 章 我 们 就 来 探 讨 分 治 与 递 归 这 两 个 概 念 密 不 可 分, 它 们 是 算 法 设 计 和 分 析 的 根 本 3.1 分 而 治 之 为 上 策 当 你 面 临 一 个 复 杂 的 问 题 时, 该 如 何 下 手 呢? 当 然 是 首 先 将 问 题 简 化, 即 将 复 杂 的 大 问 题 分 解 为 简 单 的 小 问 题, 然 后 分 而 治 之 这 正 是 算 法 里 面 一 个 非 常 重 要 的 策 略 听 说 过 中 国 古 代 总 结 出 来 的 分 治 策 略 吗? 秦 帝 国 就 是 通 过 合 纵 连 横 的 分 治 策 略 而 统 一 了 当 时 的 六 国 如 果 读 者 对 古 代 的 合 纵 连 横 不 感 兴 趣, 那 么 对 现 代 的 各 种 体 育 及 文 艺 竞 赛 总 有 点 兴 趣 吧 而 这 里 面 同 样 蕴 涵 着 分 治 的 思 想 例 如, 在 足 球 世 界 杯 赛 中 ( 见 图 3-3), 我 们 的 目 的 是 从 全 球 近 支 球 队 里 面 选 出 最 好 的, 但 直 接 在 这 么 多 的 球 队 里 面 选 择 难 度 很 大, 成 本 也 很 高 明 智 的 策 略 就 是 将 全 球 的 球 队 分 解 为 各 个 赛 区, 在 每 个 赛 区 选 出 屈 指 可 数 的 几 支 球 队 出 来, 然 后 在 这 屈 指 可 数 的 几 支 球 队 里 面 再 进 行 评 优, 这 样 难 度 和 复 杂 度 就 低 多 了 而 这 种 方 法 就 是 分 治 : 将 一 个 大 问 题 ( 在 全 球 近 支 球 队 里 面 选 优 ) 分 解 为 多 个 类 型 相 同 规 模 更 小 的 小 问 题 ( 在 每 个 赛 区 选 优 ), 分 别 解 决 小 问 题 ( 选 出 每 个 赛 区 的 优 秀 球 队 ), 最 终 使 大 问 题 迎 刃 而 解 好, 生 活 中 的 例 子 举 够 了, 下 面 我 们 用 一 个 简 单 的 数 学 例 子 来 彰 显 分 而 治 之 策 略 的 优 越 性 假 定 x 和 y 是 两 个 长 度 为 位 的 整 数, 为 方 便 起 见, 假 定 是 的 指 数 次 方 ( 不 是 指 数 次 方 也 可 以 同 样 处 理 ) 我 们 的 目 标 是 要 计 算 x 和 y 的 乘 积 如 果 我 们 直 接 用 蛮 力 相 乘 来 求 取 乘 积, 则 时 间 复 杂 性 为 这 个 时 间 复 杂 性 读 者 也 许 觉 得 并 不 坏, 但 如 果 一 个 程 序 需 要 进 行 大 量 的 乘 法 运 算, 则 这 个 时 间 复 杂 性 就 不 是 那 么 理 想 了

第 3 章 分 治 与 递 归 7 图 3-3 世 界 杯 足 球 赛 蕴 涵 着 分 治 的 思 想 那 么 有 没 有 更 好 的 算 法 呢? 有 策 略 就 是 分 治! 将 大 问 题 分 解 成 小 问 题 问 题 是 乘 法 运 算 怎 么 分 治 解 决 呢? 或 者 说 把 什 么 分 解 为 更 小 的 单 位 呢? 当 然 是 将 乘 数 和 被 乘 数 进 行 分 解 ( 难 道 还 有 别 的 东 西 可 以 分 解 的 吗 ) 首 先 将 x 和 y 分 别 分 解 为 左 右 两 半, 每 一 半 均 为 / 位 长 例 如, 如 果 x = 11111, 则 x L = 111,x R = 11 从 而 x 和 y 之 积 可 以 表 示 为 : xy = ( / x L +x R ) ( / y L +y R ) = x L y L + / (x L y R + x R y L ) + x R y R (3-1) 即 我 们 可 以 根 据 式 (3-1) 右 面 的 表 达 式 来 计 算 x 和 y 之 积 乍 一 看, 感 觉 右 边 的 表 达 式 远 比 左 边 的 xy 表 示 复 杂, 难 道 其 效 率 反 而 更 高? 那 我 们 仔 细 来 看 : 右 面 表 达 式 里 面 的 加 法 运 算 可 在 常 数 时 间 内 完 成, 的 方 次 运 算 也 可 在 线 性 时 间 内 完 成 ( 只 需 将 计 算 机 里 面 的 字 进 行 左 移 即 可 ) 因 此, 右 面 表 达 式 里 面 的 主 要 复 杂 性 在 于 其 4 个 乘 法 运 算 但 是, 这 4 个 乘 法 运 算 的 操 作 数 长 度 均 只 有 / 位, 比 原 始 的 乘 法 运 算 操 作 数 的 长 度 少 了 一 半! 这 样, 我 们 需 要 做 的 乘 法 运 算 就 是 4 ( / / 这 好 像 没 有 改 进 嘛 我 们 费 了 很 大 的 力 气 ( 耗 去 很 多 脑 细 胞 ), 却 没 有 ) 带 = 来 任 何 效 率 的 改 进 难 道 分 治 错 了 吗? 德 国 数 学 家 高 斯 很 早 就 发 现, 虽 然 两 个 复 数 的 乘 法 初 看 上 去 涉 及 4 次 实 数 乘 法 运 算, 但 实 际 上 可 以 化 简 为 3 次 实 数 乘 法 运 算 受 此 启 示, 式 (3-1) 右 面 的 部 分 也 可 以 简 化 为 3 次 乘 法 运 算, 即 计 算 x 和 y 的 乘 积 所 需 要 的 乘 法 运 算 实 际 上 是 3 个 规 模 为 / / 的 运 算, 即 3/4 你 能 看 出 来 可 以 简 化 为 怎 样 的 3 个 乘 法 运 算 吗? 这 一 下 总 算 有 了 改 进 : 从 降 到 了 3 /4 也 许 有 人 认 为 这 个 改 善 微 不 足 道, 况 且 在 第 章 论 述 渐 近 分 析 时 不 是 说 过 吗, 在 渐 近 分 析 时, 我 们 可 以 将 系 数 忽 略, 这 样 和 3 /4 在 趋 向 无 穷 的 时 候 就 是 一 回 事 了 如 果 我 们 的 分 治 仅 仅 进 行 一 步 就 停 止, 上 述 说 法 是 完 全 正 确 的 关 键 是, 我 们 为 什 么 要 停 止 继 续 分 治 呢? 如 果 式 (3-1) 右 面 可 以 改 进 为 3 个 乘 法 运 算, 那 么 这 些 乘 法 运 算 又 可 以 进 一 步 经 分 治 而 变 成 3 个 长 度 再 折 半 的 乘 法 运 算 而 我 们 可 以 一 直 这 样 递 归 分 治 下 去, 最 后 必 到 达 操 作 数 长 度 为 1 位 的 情 况, 而 此 时 的 乘 法 运 算 成 本 就 微 不 足 道 了 ( 变 为 常 数 级 ) 这 样, 我 们 的 乘 法 运 算 的 运 算 效 率 将 满 足 下 述 递 归 表 达 式 : T ( ) = 3T (/) + O () (3-) 这 里 T () 代 表 长 度 为 位 的 乘 法 运 算 按 照 式 (3-1), 它 可 以 变 为 3 个 长 度 为 / 的 乘 法 运 算 O () 是 将 3 个 长 度 为 / 的 乘 法 运 算 结 果 组 装 起 来 所 需 要 的 时 间 ( 加 法 和 移 位 操 作 )

8 第 一 篇 算 法 基 础 篇 那 么 式 (3-) 的 求 解 是 什 么 呢? 答 案 是 O ( 1.59 ), 这 是 一 个 巨 大 的 改 善 O ( 1.59 ) 的 时 间 复 杂 性 也 许 不 容 易 从 递 归 式 一 眼 看 出, 但 如 果 我 们 画 出 一 棵 递 归 树 ( 如 图 3-4 所 示 ), 则 这 种 结 果 就 较 容 易 看 出 了 图 3-4 递 归 树 帮 助 我 们 求 解 递 归 式 T() = 3T(/) + O() 这 里 的 关 键 是, 在 递 归 树 的 每 一 级, 分 支 因 子 是 3, 即 每 一 级 问 题 被 分 解 为 3 个 更 小 的 同 样 问 题 因 此, 在 第 k 级, 子 问 题 树 的 数 量 增 加 到 3 个, 但 每 个 子 问 题 的 大 小 则 为 k / k 由 于 树 的 高 度 为, 因 此, 最 后 一 级 是 k = 根 据 前 述 推 理, 这 一 级 的 工 作 量 为 O (3lg ), 通 过 变 换, 该 表 达 式 也 就 是 O ), 即 我 们 前 面 给 出 的 O ) 由 于 每 一 级 的 时 间 成 本 呈 几 何 级 数 增 加, 该 成 本 就 是 整 个 (lg3 乘 法 运 算 的 成 本 (1.59 3. 分 治 策 略 由 上 面 的 例 子 可 见, 采 取 分 而 治 之 策 略 解 决 一 个 问 题 有 三 个 步 骤 : 1) 将 问 题 分 解 为 若 干 个 小 的 子 问 题 每 个 子 问 题 与 大 问 题 同 型, 但 规 模 更 小 ) 递 归 解 决 这 些 子 问 题 3) 将 子 问 题 的 解 答 合 并, 获 得 大 问 题 的 解 答 其 中 的 第 步 递 归 解 决 这 些 子 问 题 指 的 是 按 照 同 样 的 分 治 策 略 进 行 求 解, 即 通 过 将 这 些 子 问 题 分 解 更 小 的 孙 子 问 题 来 进 行 求 解 就 这 样 一 直 分 解 下 去, 直 到 分 解 出 来 的 子 问 题 简 单 到 只 用 常 数 操 作 时 间 即 可 解 决 为 止 而 递 归 是 彰 显 分 治 优 势 的 放 大 器, 如 果 没 有 递 归, 则 分 治 策 略 的 效 果 不 是 没 有 就 是 微 不 足 道 就 像 我 们 的 分 治 乘 法 运 算, 如 果 只 分 解 一 次, 效 率 的 改 善 不 足 挂 齿 在 分 解 到 子 问 题 规 模 达 到 微 不 足 道 的 境 界 时, 子 问 题 的 解 即 可 用 常 数 时 间 求 得 然 后 我 们 反 照 递 归 的 顺 序 由 底 至 上 将 子 问 题 的 解 合 并 起 来, 逐 级 上 推 就 构 成 了 对 原 问 题 的 解 在 分 而 治 之 的 策 略 下, 真 正 的 工 作 也 由 上 述 三 个 步 骤 构 成, 即 所 有 的 工 作 分 散 于 这 三 个 地 方 : 分 解 部 分 递 归 部 分 和 合 并 部 分 而 整 个 分 而 治 之 策 略 的 时 间 复 杂 性 也 由 这 三 部 分 的 时 间 复 杂 性 之 和 构 成 由 于 在 不 断 递 归 后, 最 后 的 子 问 题 将 变 得 极 为 简 单, 以 至 于 小 学 生 都

第 3 章 分 治 与 递 归 9 能 轻 而 易 举 地 解 决, 其 解 决 的 时 间 复 杂 性 在 整 个 策 略 中 的 比 重 微 乎 其 微, 可 以 忽 略 不 计 因 此, 分 而 治 之 策 略 的 真 正 成 本 实 际 上 由 分 解 和 合 并 两 个 部 分 构 成, 即 到 底 需 要 分 解 多 少 次, 每 次 分 解 的 子 问 题 数 到 底 是 多 少? 到 底 要 合 并 多 少 次, 每 次 分 解 和 每 次 合 并 需 要 多 少 时 间? 其 中 最 为 关 键 的 是 分 解 出 来 的 子 问 题 数 每 个 子 问 题 的 大 小, 以 及 分 解 与 合 并 本 身 的 时 间 成 本 这 些 是 决 定 分 治 策 略 是 否 奏 效 的 决 定 因 素 因 此, 设 计 优 良 的 分 解 合 并 策 略 就 十 分 重 要 3.3 递 归 表 达 式 求 解 在 实 施 分 治 策 略 时, 我 们 常 常 会 碰 到 算 法 效 率 的 递 归 表 达 式 这 是 由 分 治 策 略 的 递 归 特 性 所 决 定 的 例 如, 我 们 在 使 用 分 治 求 解 乘 法 的 时 候 就 碰 到 了 T () = 3T (/) + O () 的 递 归 表 达 式 事 实 上, 标 准 分 治 策 略 的 定 义 里 面 就 包 含 着 递 归 因 此, 求 解 递 归 表 达 式 是 分 析 分 治 策 略 的 重 要 基 础 一 般 来 讲, 分 治 策 略 将 一 个 大 的 复 杂 的 问 题 划 分 为 个 同 样 的 子 问 题, 这 些 子 问 题 的 大 小 为 / 如 果 一 直 递 归 分 解 下 去, 我 们 获 得 的 算 法 时 间 复 杂 性 的 递 归 表 达 式 将 是 : T () = T (/) + f () (3-3) 这 里 的 是 每 次 分 解 时 问 题 规 模 减 小 的 因 子, 是 每 次 分 解 时 产 生 的 子 问 题 个 数,f () 是 分 解 出 ( 和 合 并 ) 个 大 小 为 / 的 子 问 题 的 成 本 很 显 然, 1,>1, 并 且 f 的 渐 近 趋 势 为 正 ( 如 果 该 函 数 渐 近 表 现 为 负 会 是 什 么 情 况?) 注 意, 如 果 1, 则 说 明 这 种 分 治 完 全 失 败, 因 为 分 解 出 来 的 子 问 题 规 模 与 原 问 题 相 当 或 超 过 了 原 问 题! 这 样, 求 解 一 个 分 而 治 之 算 法 的 时 间 效 率 就 是 求 解 上 述 递 归 表 达 式 那 么 上 述 递 归 表 达 式 的 解 是 什 么 呢? 3.3.1 递 归 树 法 对 于 很 多 人 来 说, 理 解 抽 象 的 东 西 不 如 理 解 具 体 的 东 西 来 得 容 易, 而 一 个 递 归 表 达 式 就 是 一 个 抽 象 的 东 西, 不 容 易 看 出 其 里 面 所 隐 含 的 执 行 序 列 和 规 律, 如 每 层 递 归 的 成 本 但 如 果 我 们 将 该 抽 象 表 达 式 用 图 形 的 方 式 加 以 展 开, 则 抽 象 变 具 体, 就 容 易 理 解 多 了 虽 然 不 是 所 有 抽 象 的 东 西 都 可 以 用 具 体 的 形 象 来 描 述, 但 抽 象 递 归 表 达 式 恰 恰 可 以 被 具 体 化 将 抽 象 递 归 表 达 式 具 体 化 的 最 佳 图 形 表 示 就 是 递 归 树 该 方 法 我 们 在 解 乘 法 运 算 的 递 归 表 达 式 时 已 经 使 用 过 这 种 递 归 树 给 出 的 是 一 个 算 法 递 归 执 行 的 成 本 模 型 该 模 型 以 输 入 规 模 为 开 始, 一 层 层 的 分 解, 直 到 输 入 规 模 变 为 1 为 止 而 这 个 时 候 的 解 决 方 案 已 经 是 琐 细 的 了 图 3-5 是 表 达 式 T () = T ( / 4) + T ( / ) + 的 递 归 树 很 显 然, 递 归 树 解 法 的 优 点 是 直 观, 很 多 情 况 下 我 们 可 以 直 接 看 出 来 答 案 但 缺 点 是 不 一 定 可 靠, 就 像 任 何 使 用 省 略 号 的 方 法 一 样 ( 省 略 号 到 底 是 省 略 了 什 么?) 例 如, 图 3-5 里 的 省 略 号 总 让 我 们 觉 得 这 个 结 果 不 怎 么 令 人 放 心 : 虽 然 第 1 层 第 层 的 成 本 没 有 任 何 问 题, 但 我 们 怎 么 能 断 定 没 有 画 出 的 第 3 层 的 成 本 是 (5/16) 呢? 当 然, 为 了 保 险, 我 们 可

3 第 一 篇 算 法 基 础 篇 以 画 出 第 3 层 并 验 证 结 果 就 是 (5/16), 但 第 4 层 的 结 果 又 如 何 肯 定 呢? 图 3-5 T () = T (/4) + T (/)+ 的 递 归 树 很 显 然, 将 每 一 层 都 画 出 来 并 不 现 实, 因 此, 省 略 号 就 成 为 画 递 归 树 时 不 可 缺 少 的 工 具, 而 这 个 省 略 号 就 成 为 很 多 人 心 头 解 不 开 的 疙 瘩 3.3. 替 换 解 法 既 然 递 归 树 的 结 果 不 怎 么 令 人 放 心, 那 怎 么 克 服 这 个 缺 点 呢? 当 你 对 一 个 东 西 不 是 十 分 信 服 的 时 候, 你 怎 么 办 呢? 当 然 是 进 行 验 证! 因 此, 要 解 决 递 归 树 方 法 的 可 靠 性 问 题, 只 要 在 递 归 树 方 案 上 增 加 一 个 步 骤 : 对 递 归 树 获 得 的 答 案 进 行 验 证 例 如, 我 们 已 经 从 递 归 树 获 得 表 达 式 T () = T (/4) + T (/ ) + 的 解 为 Θ ( ) 但 这 个 答 案 是 否 可 靠 呢? 只 要 加 以 证 明 即 可 根 据 Θ ( ) 的 定 义, 我 们 只 需 要 分 别 证 明 T () = O ( ) 和 T () = Ω ( ) 即 可 而 根 据 Ω ( ) 的 定 义, 我 们 只 需 要 证 明 存 在, 对 于 >, 我 们 有 T ( ) c, 这 里 c, 为 正 的 常 数 即 可 而 此 种 证 明 使 用 数 学 归 纳 法 即 可 迅 速 获 得 假 定 上 述 条 件 对 于 所 有 小 于 的 输 入 都 成 立, 则 我 们 有 : T () = T (/4) + T (/) + c (/4) + c (/) + = c +(1-11c/16) 我 们 只 要 选 择 c 16/11, 上 述 表 达 式 即 满 足 c 的 条 件 ( 你 看 出 应 取 的 是 多 少 吗?) 因 此, 我 们 确 实 证 明 了 T () = Ω( ) 证 明 T () = O ( ) 的 过 程 与 上 述 过 程 类 似 根 据 O ( ) 的 定 义, 我 们 只 需 要 证 明 存 在, 对 于 >, 有 T () c, 这 里 c, 为 正 的 常 数 即 可 同 样, 假 定 上 述 条 件 对 于 所 有 小 于 的 输 入 都 成 立, 则 我 们 有 : T () = T (/4)+T ( /)+ c (/4) + c (/) + = c -( 11c /16-1) 我 们 只 要 选 择 c 16/11, 上 述 表 达 式 即 满 足 c 的 条 件 ( 你 看 出 应 取 的 是 多 少 吗?) 因 此, 我 们 又 证 明 了 T () = O ( ) 合 并 上 述 两 个 证 明, 我 们 有 T () = Θ ( ) 这 样 我 们 对 根 据 递 归 树 展 开 所 获 得 的 答 案 就 有 完 全 的 信 心 了 仔 细 观 察 上 述 归 纳 求 证 过 程 发 现, 我 们 是 将 一 个 假 定 的 解 答 代 入 到 递 归 表 达 式, 然 后 求 解 出 最 终 结 果, 这 种 解 法 也 被 称 为 替 换 解 法 根 据 上 面 的 例 子, 我 们 看 出 使 用 替 换 解 法 的 步 骤 如 下 :

第 3 章 分 治 与 递 归 31 1) 猜 一 个 答 案 ) 使 用 归 纳 法 对 答 案 进 行 验 证 ( 根 据 猜 测 的 答 案 形 成 归 纳 假 设, 然 后 对 归 纳 假 设 进 行 验 证 ) 3) 解 决 表 达 式 中 的 常 数 当 然, 在 猜 测 一 个 答 案 的 时 候, 如 果 一 眼 看 不 出 来, 可 以 使 用 递 归 树 作 为 帮 助 例 3-1 求 解 递 归 表 达 式 T () = 4T (/) + 的 解 解 我 们 的 步 骤 如 下 : 1) 由 于 表 达 式 里 面 有 项, 我 们 猜 大 一 点, 将 解 猜 为 O ( 3 ) ) 根 据 猜 测 获 得 归 纳 假 设, 对 于 任 意 k <,T (k) ck 3 将 该 假 设 代 入 到 递 归 式 里 有 : T () = 4T (/) + 4c (/) 3 + ( 归 纳 假 设 ) = (c/) 3 + ( 代 数 变 换 ) = c 3 ((c/) 3 ) ( 所 期 值 - 剩 余 值 ) c ( 所 期 望 的 值 ) 3 3) 最 后 解 决 常 数 c 如 果 第 步 最 后 的 不 等 式 要 成 立, 则 必 须 满 足 (c/) 3 而 这 个 条 件 在 c 且 1 的 时 候 成 立 这 里 需 要 注 意 的 是, 在 上 述 证 明 过 程 中, 我 们 没 有 考 虑 初 始 条 件, 而 初 始 条 件 是 归 纳 法 能 够 成 立 的 基 础 那 么 上 述 归 纳 证 明 的 初 始 条 件 是 什 么 呢? 当 然 是 T(1) c 这 个 条 件 成 立 吗? 当 然, 只 要 选 择 足 够 大 的 c 1 即 可 由 于 大 多 数 时 候 初 始 条 件 的 满 足 显 而 易 见, 我 们 在 证 明 时 通 常 忽 略 这 个 步 骤 我 们 只 在 初 始 条 件 的 满 足 并 不 明 显 的 时 候 才 会 单 独 对 初 始 条 件 进 行 讨 论 至 此, 我 们 证 明 了 T () = 4T (/) + 的 上 限 为 O ( ), 但 这 个 上 限 对 我 们 并 没 有 太 大 帮 3 助, 因 为 太 松 了 该 上 限 并 不 是 我 们 讨 论 的 递 归 表 达 式 的 一 个 最 紧 的 上 限! 而 一 个 不 紧 的 上 限 有 可 能 导 致 误 解 : 我 们 可 能 认 为 T () = 4T(/) + 的 效 率 是 立 方 级 的! 而 事 实 却 不 是 那 怎 么 办 呢? 当 然 是 猜 一 个 更 紧 的 上 限, 如 平 方 级, 即 猜 T () = O ( ) 那 么 这 个 猜 想 是 否 正 确 呢? 只 要 用 归 纳 法 来 证 一 下 即 知 设 对 于 任 意 k <,T ( k, 将 其 代 入 递 归 式 我 们 有 : ) ck T () = 4T ( / ) + 4c ( / ) + = c + = c ( ) 令 人 遗 憾 的 是,c ( ) 无 论 在 什 么 情 况 下 ( 无 论 怎 么 选 择 c) 也 不 会 小 于 c 我 们 的 证 明 似 乎 陷 入 了 僵 局 难 道 我 们 的 猜 想 有 问 题 吗? 如 果 画 一 棵 递 归 树, 你 会 发 现 我 们 的 猜 想 似 乎 是 正 确 的 也 许 是 我 们 的 证 明 错 了? 而 改 正 的 方 法 是 增 强 我 们 的 递 归 假 设! 即 如 果 证 明 不 了 一 个 假 设, 那 就 证 明 一 个 更 难 的 假 设! 这 听 上 去 似 乎 反 直 觉, 但 谁 说 过 算 法 是 一 个 靠 直 觉 的 学 科 呢?( 有 兴 趣 的 读 者 可 参 阅 计 算 机 的 心 智 : 操 作 系 统 之 哲 学 原 理 一 一 书 对 直 觉 与 非 直 觉 学 科 的 讨 论 ) 我 们 的 反 直 觉 思 维 是 这 样 的 : 重 新 设 计 归 纳 假 设, 使 得 其 比 前 面 的 归 纳 假 设 更 严 格 新 的 归 纳 假 设 为 对 于 所 有 k <,T (k) c 1 k c k 在 新 的 假 设 下, 我 们 有 : 一 该 书 已 由 机 械 工 业 出 版 社 出 版, 书 号 为 ISBN 978-7-111-664-6

3 第 一 篇 算 法 基 础 篇 T () = 4T ( /) + 4(c 1 (/) c (/)) + = c 1 c + = c 1 c (c ) c 1 c 上 述 最 后 一 行 的 不 等 式 成 立 的 条 件 是 (c )>, 而 该 不 等 式 在 c 1 的 情 况 下 就 成 立 当 然 了, 我 们 还 需 要 选 择 足 够 大 的 c 1 来 满 足 初 始 条 件 ( 这 个 初 始 条 件 是 什 么?) 3.3.3 大 师 解 法 替 换 解 法 虽 然 比 递 归 树 解 法 可 靠, 但 也 存 在 诸 多 缺 陷 第 一 个 缺 陷 是 要 将 答 案 猜 得 不 多 不 少 并 不 容 易 猜 松 了 会 导 致 误 解, 猜 紧 了 又 证 明 不 出 来 其 次, 即 使 猜 测 的 答 案 正 确, 也 不 一 定 能 够 容 易 地 证 明 我 们 上 面 的 例 子 已 经 说 明 了 这 一 点 再 次, 这 种 方 法 只 能 针 对 具 体 的 递 归 表 达 式, 而 不 能 对 抽 象 的 递 归 表 达 式 进 行 求 解 例 如, 对 于 T () = T (/) + f () 的 抽 象 递 归 式, 替 换 解 法 就 只 能 望 洋 兴 叹 了 那 有 没 有 更 好 的 办 法, 既 能 克 服 替 换 解 法 的 缺 点, 又 能 对 抽 象 的 递 归 式 进 行 一 般 求 解 呢? 我 们 先 来 将 抽 象 的 递 归 式 进 行 展 开 看 看 能 得 到 什 么 结 果 T () = T ( / ) + f () = T ( / ) + f ( / ) + f () = 3 T ( / 3 ) + f ( / ) + f ( / ) + f ( ) T(1) + f + + f + f + f ( ) 1 1 = = T(1) 1 f + = = Θ ( ) + 1 f (3-4) = 到 这 一 步, 我 们 已 经 将 抽 象 递 归 式 分 解 为 两 大 块 : 一 部 分 是 Θ ( ), 这 是 一 个 恒 定 的 数 量 级, 另 一 部 分 似 乎 是 一 个 类 似 级 数 的 求 和 根 据 渐 近 表 示 的 性 质 3, 两 项 之 和 的 数 量 级 小 于 两 项 之 中 较 大 项 的 数 量 级 因 此, 我 们 只 要 将 第 二 项 和 式 与 Θ ( ) 比 较, 取 其 较 大 者 即 可 而 对 于 第 二 项 和 式 来 说, 都 是 常 数, 起 主 导 作 用 的 是 函 数 f 的 渐 近 数 量 级 因 此, 我 们 只 要 比 较 函 数 f 和 Θ ( ) 即 可 而 对 两 个 函 数 进 行 比 较 的 结 果 只 有 4 种 可 能 : 大 于 小 于 等 于 和 不 能 相 比 下 面 就 这 4 种 情 况 分 别 进 行 讨 论 1.f()< Θ( ), 即 函 数 f 的 数 量 级 小 于 Θ( ) 在 这 种 情 况 下, 不 失 一 般 性 ( 为 什 么 ), 我 们 假 定 f ( ) = O ( ), 这 里 于 的 常 数, 也 就 是 说,f () 比 的 渐 近 增 长 要 慢, 且 慢 一 个 因 子 是 一 个 大

第 3 章 分 治 与 递 归 33 此 时 式 (3-4) 最 右 面 的 一 项 可 以 化 简 如 下 : = = = = = 1 1 1 f ( / O O ) 因 此, 我 们 有 :T() = Θ( 1 1 = O O = = = 1 1 O = = O = = 1 = O ( ) = 1 1 = O = O 1 1 = O ( ) = O ( ) ) + O( )= Θ(. f ()= Θ( ) 此 时 式 (3-4) 最 右 面 的 一 项 可 以 化 简 如 下 : ) 1 1 1 f ( / ) = Θ = Θ = = = 1 1 =Θ 1 ( ( )) =Θ =Θ = = ) + Θ ( ( )) = Θ ( ()) 因 此, 我 们 有 :T () = Θ ( 实 际 上, 这 个 条 件 我 们 还 可 以 放 松 到 Θ ( lg )( 因 为 对 数 级 离 常 数 级 的 距 离 远 小 于 k 其 与 线 性 级 的 距 离 ), 这 里 的 k 为 一 个 常 数, 即 f() 与 Θ( ) 比 较 在 一 个 对 数 级 范 围 内 波 动 此 时 式 (3-4) 最 右 面 的 一 项 可 以 化 简 如 下 : 1 1 k ( / ) lg f = Θ = = 1 1 k k k =Θ lg (lg lg ) =Θ = = 1 k k =Θ (l g l g ) =Θ 1 1 k k lg lg = = =

34 第 一 篇 算 法 基 础 篇 1 1 k k lg lg = = 1 k k k+ 1 lg lg 1g ( lg ) =Θ =Θ =Θ = lg ) k+1 因 此, 我 们 有 :T () = Θ ( ) +Θ( lg k+1 ) = Θ( 细 心 的 读 者 可 能 已 经 看 出 来, 这 是 前 面 情 况 的 一 般 化, 或 者 前 面 是 后 面 在 k= 时 的 特 例 3. f () 的 渐 近 增 长 趋 势 > Θ( ) 在 此 情 况 下, 由 于 又 由 于 f () >Θ( = f (/ 1 )> f ()( 正 数 项 的 和 大 于 和 里 面 的 每 一 项 ), 我 们 有 : 1 = f (/ ) = Ω( f ()) ), 式 (3-4) 的 时 间 效 率 将 完 全 由 1 = f ( / ) 决 定 因 此, T() = Ω( f()) 至 此 我 们 找 出 了 递 归 表 达 式 的 下 限 但 仅 仅 找 出 下 限 是 没 有 多 大 意 思 的, 因 为 我 们 只 知 道 该 递 归 表 达 式 的 效 率 最 好 只 可 能 是 f () 而 我 们 更 想 知 道 的 是 T () 的 上 限 根 据 题 意, T () 的 上 限 就 是 f (/ ) 的 上 限 但 是 f (/ ) 的 上 限 是 什 么 呢? 我 们 先 来 看 看 函 数 f 代 表 的 意 思 :f 代 表 的 是 分 治 策 略 中 的 分 解 ( 成 子 问 题 ) 和 合 并 ( 子 问 题 ) 的 成 本 由 于 f () 的 渐 近 增 长 趋 势 >Θ( ), 该 分 治 策 略 的 分 解 和 合 并 成 本 高 于 子 问 题 的 解 决 成 本, 即 分 解 和 合 并 成 本 高 于 解 决 问 题 的 成 本 而 如 果 要 在 这 种 情 况 获 得 解, 分 解 和 合 并 的 成 本 应 该 逐 级 下 降 ; 否 则, 分 解 和 合 并 成 本 随 着 分 解 的 推 进 将 呈 发 散 态 势, 这 样 总 成 本 有 可 能 不 会 收 敛 那 么 这 种 分 治 策 略 显 然 就 没 有 什 么 意 义 了, 或 者 说, 我 们 的 分 治 策 略 应 用 错 了! 而 如 果 分 解 与 合 并 成 本 逐 级 下 降, 则 意 味 着 函 数 f 满 足 f (/) cf (), 这 里 c <1 是 一 个 正 常 数 这 时 我 们 可 以 很 快 获 得 式 (3-4) 的 上 限 如 下 : 1 1 1 ( / ) ( ) ( ) ( ) ( ( )) f c f f c = f = O f c 1 = = = 合 并 我 们 前 面 的 下 限 解 f (/ ) = Ω( f ()), 我 们 有 f (/ ) = Θ( f ()) 因 此, T () = Θ( ) + Θ( f ()) = Θ( f ())( 因 为 f () 大 于 ) 因 此 我 们 的 解 为 T ( ) = Θ ( f ()), 这 也 是 我 们 所 猜 测 的 结 果 ( 你 预 料 到 这 个 结 果 了 吗?)

第 3 章 分 治 与 递 归 35 4. 无 法 比 较 这 种 情 况 目 前 尚 无 一 般 规 律 可 循, 求 解 需 要 个 人 的 灵 感 和 聪 明 才 智 上 面 所 介 绍 4 种 情 况 中 前 三 种 情 况 都 有 规 律 可 循, 而 这 三 种 情 况 适 用 的 情 景 很 多, 具 有 较 大 普 遍 性, 可 应 用 于 各 种 分 治 场 合, 因 此 被 称 为 大 师 解 法 如 果 使 用 递 归 树, 则 大 师 解 法 的 直 观 意 义 就 很 显 然 了 ( 如 图 3-6 所 示 ) 图 3-6 大 师 解 法 的 递 归 树 演 示 大 师 解 法 的 第 一 种 情 况 代 表 的 是 递 归 树 的 每 层 成 本 从 根 至 下 呈 几 何 级 数 增 长, 成 本 在 叶 子 一 层 达 到 最 高, 即 最 后 一 次 递 归 是 整 个 递 归 过 程 中 成 本 最 高 的 一 次 因 此 递 归 分 治 的 总 成 本 在 渐 近 趋 势 上 与 叶 子 层 成 本 一 样, 即 成 本 为 Θ ( ) 大 师 解 法 的 第 二 种 情 况 对 应 的 递 归 树 状 态 是 每 层 成 本 一 样 ( 在 渐 近 趋 势 上 ), 即 每 层 成 本 均 为 由 于 一 共 有 lg 层, 因 此, 总 成 本 为 每 一 层 的 成 本 乘 以 lg, 即 Θ ( lg) 大 师 解 法 的 第 三 种 情 况 对 应 的 递 归 树 状 态 为 每 层 成 本 呈 几 何 级 数 递 减, 树 根 这 一 层 的 成 本 占 主 导 地 位 因 此, 总 成 本 就 是 树 根 层 的 成 本, 即 Θ ( f ()) 到 这 里, 大 师 解 法 就 介 绍 完 了 但 细 心 的 读 者 可 能 还 发 现, 我 们 在 证 明 大 师 解 法 的 过 程 中 只 考 虑 了 被 整 除 的 情 况 那 么 不 能 整 除 的 情 况 是 否 结 论 也 是 一 样 呢? 这 个 问 题 就 留 给 读 者 考 虑 吧 3.4 分 治 策 略 举 例 1: 乘 方 运 算 乘 方 运 算 就 是 对 一 个 数 取 若 干 次 方 的 运 算, 也 就 是 自 己 乘 以 自 己 若 干 次 问 题 的 具 体 定 义 如 下 : 对 于 N, 计 算 如 果 不 假 思 索, 直 接 进 行 次 乘 法, 则 一 共 需 要 进 行 次 乘 法 即 这 种 天 真 的 算 法 的 效 率 是 Θ () 次 乘 法 ( 每 次 乘 法 本 身 的 效 率 我 们 这 里 并 不 考 虑, 因 为 它 不 影 响 我 们 的 分 析 ) 但 是 如 果 仔 细 分 析, 我 们 发 现 : / /, 如 果 偶 数 = ( 1) / ( 1) /, 如 果 是 奇 数

36 第 一 篇 算 法 基 础 篇 这 样, 我 们 就 可 以 应 用 分 治 策 略, 将 次 方 的 乘 方 运 算 变 为 两 个 / 次 方 的 乘 方 运 算 和 一 次 普 通 的 乘 法 运 算 ( 或 两 个 (-1)/ 次 方 的 乘 方 运 算 和 两 次 普 通 的 乘 法 运 算 ) 如 果 再 看 仔 细, 会 发 现 分 解 出 的 两 个 /( 或 (-1)/) 次 方 的 乘 方 运 算 实 际 上 是 同 一 个 乘 方 运 算! 因 此, 我 们 可 以 将 这 种 分 治 策 略 的 递 归 表 达 式 写 为 :T () = T (/) + Θ(1) 这 里 T () 为 分 治 策 略 的 效 率,Θ(1) 表 示 每 次 分 解 后 合 并 答 案 所 需 的 时 间 ( 常 数 次 乘 法 ) 从 我 们 的 大 师 解 法 可 以 得 出 该 递 归 表 达 式 的 解 为 :T () = Θ (lg) 由 此 可 见, 分 治 策 略 比 起 天 真 的 直 接 解 法 效 率 要 高 得 多! 3.5 生 命 不 能 承 受 之 重 : 矩 阵 乘 法 矩 阵 乘 法 是 另 一 个 使 用 分 治 策 略 的 好 地 方 由 于 科 学 计 算 中 大 量 使 用 矩 阵 乘 法, 高 效 率 地 解 决 这 个 问 题 显 然 意 义 重 大 下 面 我 们 先 看 看 矩 阵 乘 法 的 定 义 定 义 给 定 两 个 矩 阵 A B, 记 A = [ i ], B = [ i ] (i, = 1,,, ) 那 么 A B 的 乘 积 矩 阵 C = [c i ] = A B (i, = 1,,, ), 即 c c 11 1 c 1 11 1 1 11 1 1 c c c 1 1 1 = = c c c 1 1 1 记 为 : c i = ik k k = 1 如 果 使 用 直 接 相 乘 的 办 法 来 计 算, 则 矩 阵 乘 法 的 算 法 如 下 : for i 1 to do for 1 to do c i for k 1 to do c i c i + ik k 显 而 易 见, 这 个 天 真 的 解 法 的 时 间 复 杂 性 是 Θ( 3 )( 以 乘 法 和 加 法 次 数 为 单 位 ) 也 许 读 者 觉 得 三 次 方 的 矩 阵 乘 法 效 率 并 不 差, 但 是 如 果 考 虑 到 矩 阵 乘 法 在 很 多 领 域 是 一 种 使 用 非 常 频 繁 的 操 作, 且 在 这 些 领 域 里, 每 个 矩 阵 的 规 模 巨 大, 那 么 这 种 天 真 解 法 并 不 令 人 满 意 有 更 好 的 办 法 吗? 有, 分 治 呀 由 于 直 接 矩 阵 乘 法 的 时 间 复 杂 性 高 (O (3 )), 我 们 自 然 想 到 能 否 采 取 分 而 治 之 的 策 略 来 提 高 效 率, 即 将 两 个 将 要 进 行 乘 法 运 算 的 矩 阵 划 分 为 4 个 大 小 一 样 的 小 矩 阵, 分 别 求 出 这 些 小 矩 阵 的 相 关 乘 积, 再 进 行 组 合

第 3 章 分 治 与 递 归 37 我 们 的 思 考 是 将 一 个 的 矩 阵 分 解 为 个 (/) (/) 的 子 矩 阵, 求 得 这 些 子 矩 阵 的 乘 积 后 再 进 行 组 装 而 获 得 原 来 大 矩 阵 的 乘 积 即 r s e f = t u c d g h C = A * B 这 样, 原 来 的 矩 阵 乘 法 可 以 变 为 下 面 的 8 个 子 矩 阵 乘 法 和 4 个 加 法 操 作 : r = e + g s = f + h t = ce + dg u = cf + dh 上 述 的 8 个 子 矩 阵 乘 法 又 可 以 递 归 使 用 上 述 分 治 策 略, 从 而 获 得 递 归 表 达 式 如 下 : T () = 8T (/) + Θ ( ) 上 面 式 子 里 面 的 8T(/) 表 示 8 个 (/) 大 小 的 子 矩 阵 乘 法,Θ ( ) 表 示 将 子 矩 阵 乘 积 相 加 的 时 间 复 杂 性 而 根 据 大 师 解 法 : 8 = = 情 况 1 3 T () = Θ ( 3 ) 虽 然 这 种 分 解 办 法 将 问 题 分 解 为 8 个 大 小 为 原 来 一 半 的 问 题, 但 使 用 大 师 解 法 后 发 现, 这 种 办 法 的 时 间 复 杂 性 仍 然 为 O ( ) 难 道 分 而 治 之 策 略 在 矩 阵 乘 法 上 派 不 上 用 场 吗 3? 分 治 错 了 吗? 答 案 取 决 于 你 能 否 将 递 归 式 子 里 面 的 8 个 子 矩 阵 乘 法 减 少 一 个 或 几 个 如 果 能, 则 分 治 就 有 效 果 ; 如 果 不 能, 则 分 治 就 是 多 此 一 举 幸 运 的 是, 我 们 确 实 可 以 将 递 归 式 子 里 面 的 8 降 低 到 7 仔 细 分 析 发 现, 我 们 实 际 上 可 以 用 7 个 子 问 题 来 取 代 正 常 分 解 下 需 要 的 8 个 子 问 题, 即 分 解 后 我 们 只 需 要 进 行 7 次 子 矩 阵 的 乘 法 运 算, 而 不 是 原 来 的 8 次 这 个 发 现 由 德 国 数 学 家 沃 卡 斯 特 劳 森 (Volker Strsse) 所 做 出 下 面 给 出 这 个 从 8 降 低 到 7 的 过 程 首 先, 进 行 如 下 7 个 子 矩 阵 乘 法 运 算 : P 1 = ( f h) P = ( + ) h P 3 = ( c + d ) e P 4 = d ( g e) P 5 = ( + d ) (e + h) P 6 = ( d ) ( g + h) P 7 = ( c) (e + f ) 然 后, 对 前 面 的 中 间 结 果 再 进 行 加 减 运 算, 即 获 得 最 后 的 结 果 如 下 : r = P 5 + P 4 P + P 6 s = P 1 + P t = P 3 + P 4 u = P 5 + P 1 P 3 P 7

38 第 一 篇 算 法 基 础 篇 例 如 : r = P 5 + P 4 P + P 6 = ( + d) (e + h) + d ( g e) ( + )h + ( d ) (g + h) = e + h + de + dh + dg de h h + g + h dg dh = e + g 这 样 我 们 一 共 需 要 7 次 乘 法 18 次 加 法 和 减 法 递 归 表 达 式 改 变 为 : T () = 7T (/) + Θ ( ) 按 照 大 师 解 法 我 们 有 : 7 = 情 况 1.81 7 T () = Θ( ) Θ (.81 ) 也 许.81 与 3 比 较 起 来 没 有 多 大 区 别, 但 要 想 到 这 个 数 字 出 现 的 位 置 是 幂 上 面, 其 所 带 来 的 效 率 改 善 是 非 常 可 观 的, 尤 其 是 在 很 大 的 时 候! 事 实 上, 在 3 时, 斯 特 劳 森 的 算 法 就 已 经 超 越 了 天 真 的 直 乘 法 由 于 矩 阵 乘 法 在 天 文 地 理 气 象 等 诸 多 方 面 有 着 极 为 广 泛 的 应 用, 人 们 一 直 在 持 久 地 努 力 改 善 矩 阵 乘 法 的 效 率, 到 目 前 为 止 最 好 的 算 法 能 够 达 到 的 效 率 为 Θ(.376 ) 不 过 这 个 数 量 级 只 在 理 论 上 成 立 或 者 只 针 对 某 种 特 定 规 模 的 矩 阵 乘 法 才 成 立, 在 实 际 的 计 算 机 上 针 对 通 用 的 矩 阵 乘 法 规 模 运 行 时, 则 通 常 不 能 实 现 这 个 效 率 3.6 魔 鬼 序 列 : 斐 波 那 契 序 列 公 元 1 年, 比 萨 的 列 奥 纳 多 (Leordo of Pis, 又 被 称 为 斐 波 那 契 (Fiocci)) 在 他 的 算 经 (Lier Aci) 一 书 里 谈 到 了 斐 波 那 契 序 列 这 个 序 列 是 因 为 描 述 理 想 状 态 下 兔 子 的 数 量 增 长 而 得 出 的 ( 见 图 3-7) 该 兔 子 增 长 模 型 如 下 : 原 点 一 对 ( 雌 雄 ) 兔 子 规 律 每 对 兔 子 每 个 月 产 下 一 对 兔 子, 且 一 生 只 能 产 两 次, 并 且 在 第 二 次 生 产 后 老 死 1) 第 个 月, 只 有 一 对 ( 雌 雄 ) 兔 子, 而 额 外 的 兔 子 对 数 为 ( 相 对 于 原 始 兔 子 对 数 而 言 ) ) 第 1 个 月, 这 对 初 始 的 兔 子 生 下 一 对 小 兔 子, 即 额 外 的 兔 子 对 数 为 1( 相 对 第 个 月 ) 3) 第 个 月, 两 对 兔 子 各 生 下 一 对 兔 子, 最 先 的 那 对 兔 子 老 死 额 外 的 兔 子 对 数 为 1 ( 相 对 第 1 个 月 ) 4) 第 3 个 月, 剩 下 的 三 对 兔 子 各 生 下 一 对 兔 子, 最 老 的 一 对 兔 子 老 死, 额 外 的 兔 子 对 数 为 ( 相 对 第 个 月 ) 5) 如 果 定 义 第 个 月 的 兔 子 数 量 为 F () 由 于 这 个 时 刻 只 有 在 第 - 个 月 还 活 着 的 兔 子 才 能 产 下 后 代, 因 此,F ( ) 对 兔 子 加 上 当 前 的 兔 子 数 量 F ( 1) 就 是 第 个 月 的 兔 子 数 量, 即 F () = F ( 1) + F ( ) 斐 波 那 契 序 列 是 一 个 非 常 有 趣 且 故 事 很 多 的 序 列 有 人 说, 它 是 一 个 和 谐 完 美 的 数 列 ; 有 人 说, 其 实 斐 波 那 契 序 列 并 不 是 由 列 奥 纳 多 首 次 提 出 的, 它 在 古 印 度 就 已 经 存 在 了, 当 时

第 3 章 分 治 与 递 归 39 被 应 用 在 诗 文 的 韵 律 上 ; 有 人 说, 它 是 鹦 鹉 螺 壳 上 面 的 纹 路 的 数 字 体 现 ; 又 有 人 说, 它 趋 向 于 黄 金 分 割 ; 还 有 人 说, 它 是 魔 鬼 序 列, 里 面 隐 藏 着 魔 鬼 ( 即 撒 旦 ) 引 诱 人 类 犯 罪 的 证 据 各 种 说 法 扑 朔 迷 离, 不 一 而 足 图 3-7 斐 波 那 契 序 列 与 兔 子 的 数 量 存 在 着 密 切 的 关 系 我 们 看 一 下 该 序 列 的 前 几 项 以 点 数 来 排 开 的 效 果, 见 图 3-8 你 觉 得 很 优 美 吗? 如 果 我 们 将 其 排 成 图 3-8 的 样 子, 你 又 能 看 出 何 种 名 堂? 什 么 也 没 看 出 来 吗? 不 会 吧 仔 细 看! 图 3-8 斐 波 那 契 序 列 的 各 种 图 示 当 然, 本 书 不 去 探 讨 该 序 列 的 种 种 神 奇 传 说, 及 其 与 魔 鬼 的 千 丝 万 缕 的 联 系 我 们 关 心 的 是 如 何 求 取 该 数 列 中 任 意 一 项 的 值 例 如 F 1 这 个 问 题 也 许 看 上 去 稀 松 平 常 求 取 F 1, 那 不 是 很 简 单 吗, 它 等 于 F 99 +F 98 呀! 那 F 99 和 F 98 的 值 是 什 么 呢? 简 单 呀, 分 别 是 F 98 +F 97 和 F 97 +F 96 这 样 一 直 递 归 下 去, 直 到 F 1 和 F, 不 就 获 得 F 1 的 值 了 吗?

4 第 一 篇 算 法 基 础 篇 这 个 办 法 从 概 念 上 看 倒 是 不 错, 但 这 个 算 法 的 效 率 是 多 少 呢? 我 们 将 这 个 问 题 推 广 一 下, 考 虑 F 的 计 算 显 而 易 见, 上 述 递 归 要 一 直 到 F 和 F 1 才 结 束 因 此, 要 获 得 此 算 法 的 效 率, 就 需 要 知 道 有 多 少 个 F 1 和 F 由 于 F 1 不 再 需 要 递 归, 而 比 F 1 大 的 F 递 归 时 会 同 时 产 生 F 1 和 F, 因 此,F 1 的 个 数 要 多 于 F 所 以 倍 F 1 的 个 数 要 多 于 F 1 和 F 个 数 之 和 因 此, 上 述 算 法 的 效 率 完 全 由 F 1 的 个 数 决 定 那 么 这 种 递 归 算 法 会 产 生 多 少 个 F 1 呢? 由 于 递 归 一 直 到 F 1 和 F 结 束, 而 F 的 值 为,F 1 的 值 为 1, 因 此, 递 归 产 生 的 F 1 个 数 就 是 F 的 值, 即 上 述 算 法 的 时 间 复 杂 性 就 是 F 那 么 F 是 多 少 呢? 我 们 将 斐 波 那 契 的 递 归 表 达 式 重 新 表 述 一 下 : F (+) = F (+1) + F () 则 可 以 得 出 该 线 性 递 归 公 式 的 特 征 方 程 为 x = x+1 解 该 特 征 方 程 可 得 到 它 的 两 个 根 为 :φ 和 1+ 5 1-φ, 这 里 φ = 1+ ( 看 出 来 这 是 什 么 了 吗?) 将 F 用 上 面 的 两 个 方 程 根 表 示, 有 F = yφ + z(1- φ) 将 F 和 F 1 的 值 代 入, 可 获 得 y = 1/ 5,z = -1/ 5 如 此, 我 们 获 得 F 的 通 式 为 :F = 1 [ φ (1 φ) ] 由 于 φ > 1 时, 我 们 有 : φ 5, 当 趋 向 无 穷 时, φ 会 在 渐 近 趋 势 上 大 于 (1 φ), 即 当 趋 向 无 穷 F ϕ / 5 因 此, 递 归 解 法 需 要 计 算 的 F 1 的 次 数 为 指 数 次 方, 这 就 是 天 真 递 归 解 法 的 效 率, 非 常 低! 那 我 们 可 以 对 此 加 以 改 进 吗? 下 面 我 们 给 出 三 种 改 进 方 式 1. 由 底 至 上 很 显 然, 天 真 的 递 归 算 法 里 重 复 计 算 了 很 多 的 F 1 和 F, 如 果 想 消 除 这 些 重 复 计 算, 我 们 可 以 由 底 至 上, 从 F 和 F 1 开 始, 按 照 F, F 1, F,, F 的 顺 序 一 个 个 往 上 计 算, 这 样 就 可 以 避 免 重 复 显 然, 这 种 算 法 的 效 率 就 是 Θ ()( 次 计 算 ) 这 是 一 个 很 大 的 效 率 改 进!. 使 用 通 式 当 然, 既 然 我 们 已 经 确 定 F () 的 通 式, 为 什 么 不 直 接 使 用 通 式 来 计 算 F 呢? 由 于 要 计 算 次 方, 该 算 法 的 效 率 乃 为 Θ ()( 次 乘 法 运 算 ) 与 由 底 至 上 的 效 率 一 样! 当 然, 我 们 还 可 以 利 用 前 面 讨 论 过 的 乘 方 运 算 的 优 化 算 法, 即 递 归 求 平 方, 可 将 算 法 效 率 提 高 到 Θ (lg)( 次 乘 法 运 算 ) 与 由 底 至 上 的 效 率 相 比, 有 很 大 的 提 高!

第 3 章 分 治 与 递 归 41 但 这 种 办 法 的 问 题 是 通 式 中 有 无 理 数, 有 可 能 导 致 精 度 问 题 这 里 需 要 注 明 的 是, 如 果 人 工 使 用 通 式 计 算 F, 不 会 产 生 任 何 精 度 问 题 这 是 因 为 通 式 中 的 无 理 数 5 都 会 在 代 数 演 算 中 被 约 去, 获 得 的 数 全 部 是 精 确 的 整 数! 但 是 我 们 不 太 可 能 由 人 工 来 计 算 F 1,F 1 等, 这 太 繁 琐 了, 谁 愿 意 去 求 一 个 式 子 的 1 次 1 次 方 呢? 因 此, 我 们 还 是 要 求 助 于 计 算 机 这 样 问 题 就 来 了 : 计 算 机 不 会 进 行 约 去 操 作, 它 只 能 将 式 子 的 数 值 直 接 按 浮 点 数 进 行 运 算, 从 而 就 会 带 来 精 度 问 题! 那 还 有 更 好 的 算 法 吗? 直 白 地 说, 我 们 需 要 的 是 既 有 精 度, 又 有 效 率 (Θ()) 的 算 法 3. 使 用 矩 阵 乘 方 使 用 矩 阵 乘 方? 矩 阵 乘 法 不 是 效 率 很 低 的 一 种 运 算 吗? 没 错 矩 阵 乘 法 的 运 算 效 率 是 低, 但 前 提 是 矩 阵 的 维 数 不 断 增 大 如 果 矩 阵 的 维 数 保 持 在 一 个 很 小 的 不 变 值 上 面, 如, 则 这 种 矩 阵 的 乘 法 就 和 一 般 的 数 的 乘 法 在 一 个 数 量 级 上! 那 么 使 用 哪 一 个 矩 阵 呢? 由 于 斐 波 那 契 数 列 是 一 个 二 阶 递 推 数 列, 所 以 存 在 一 个 维 的 矩 阵 A, 使 得 (F +, F +1 ) = (F +1, F ) A 代 入 斐 波 那 契 数 列 前 几 项 的 值, 可 获 得 A 为 (F +, F +1 ) = (F +1, F ) 1 1 1 1 1 1, 即 = (F, F 1 ) 1 1 1 = (F 1, F ) 1 1 1 F+ 当 然, 我 们 也 可 以 将 表 达 式 写 作 另 外 一 种 形 式 : 1 F 1 1 = F F 1 1 这 样, 求 解 F 就 变 成 求 解 矩 阵 A 的 次 方! 而 根 据 我 们 前 面 获 得 的 乘 方 运 算 结 果 可 知, 该 操 作 的 效 率 是 Θ ( lg ) 更 为 重 要 的 是, 矩 阵 A 的 次 方 的 计 算 结 果 没 有 浮 点 误 差! 3.7 VLSI 布 线 在 本 章 结 束 之 前, 我 们 再 看 一 个 实 际 中 经 常 遇 到 的 问 题 :VLSI 布 线 问 题 布 线 是 集 成 电 路 设 计 里 面 一 个 重 要 的 方 面 布 线 的 时 候 要 考 虑 的 因 素 很 多 : 线 与 线 之 间 的 间 距 输 入 线 的 散 入 限 制 输 出 线 的 散 出 限 制 线 的 最 大 长 度 限 制 等 这 里 有 一 个 故 事, 讲 的 是 某 大 学 生 初 到 一 家 公 司 上 班 的 时 候, 老 板 给 他 布 置 了 一 个 芯 片 布 局 设 计 的 任 务, 并 问 他 要 多 长 时 间 可 以 设 计 出 来 这 个 学 生 不 假 思 索 地 说 : 一 个 星 期! 老 板 一 听, 惊 奇 得 很, 心 想 国 内 名 牌 大 学 的 学 生 就 是 厉 害, 一 个 星 期 就 能 将 一 个 复 杂 的 芯 片 布 局 设 计 搞 定! 一 个 星 期 后, 这 个 大 学 生 将 设 计 图 交 给 了 老 板 老 板 一 看, 什 么 也 没 说, 就 让 他 离 开 公 司 了 原 来 这 个 大 学 生 设 计 的 图 纸 没 有 考 虑 到 线 与 线 之 间 的 间 距 散 入 和 散 出 限 制 散 热 及 + 1

4 第 一 篇 算 法 基 础 篇 晶 片 面 积 最 小 化 等 问 题, 而 只 是 画 了 一 张 图 将 各 种 器 件 按 照 逻 辑 关 系 连 接 起 来 而 已! 好 了, 闲 话 少 说,VLSI 布 线 的 问 题 就 是 要 在 一 个 尽 量 小 的 空 间 里 面 布 置 好 各 种 元 件, 并 且 达 到 散 入 散 出 散 热 间 距 等 要 求 例 如, 为 了 使 布 线 工 艺 尽 量 简 单, 我 们 要 对 芯 片 里 面 元 器 件 的 布 局 为 一 棵 完 全 二 叉 树 的 形 式 这 样 我 们 的 VLSI 布 线 问 题 就 变 成 如 何 将 一 个 有 个 叶 子 的 完 全 二 叉 树 放 置 在 一 个 空 间 尽 量 小 的 网 格 里 面? 一 个 天 真 直 观 的 布 线 就 是 将 二 叉 树 原 封 不 动 地 挪 到 网 格 上, 形 成 如 图 3-9 所 示 的 布 局 图 3-9 完 全 二 叉 树 在 芯 片 晶 格 里 面 的 直 接 排 列 方 式 此 种 布 局 占 用 的 宽 度 和 高 度 分 别 为 w ( 和 ) h ( ) 关 键 是 这 个 宽 度 和 高 度 分 别 是 什 么 呢? 从 布 局 图 看 到, 一 个 叶 节 点 数 为 的 完 全 二 叉 树 需 要 占 用 的 高 度 是 h ( ), 是 一 个 叶 节 点 数 为 / 的 完 全 二 叉 树 的 高 度 加 1, 即 h ( ) = h (/) + Θ(1) = Θ(lg) 而 宽 度 w ( 则 是 一 个 叶 节 点 数 为 ) / 的 完 全 二 叉 树 的 宽 度 的 倍 加 1, 即 w ( ) = w (/) + Θ(1) = Θ() 这 样 此 种 布 局 所 占 的 空 间 大 小 为 Θ (lg) 这 是 最 优 的 布 局 吗? 显 然 不 是, 因 为 很 多 空 间 都 浪 费 掉 了 : 如 图 中 最 上 面 一 行 只 有 一 个 节 点, 其 他 节 点 都 空 着! 而 第 二 行 只 有 个 节 点, 其 他 节 点 都 空 着! 很 显 然, 这 个 问 题 非 常 适 合 使 用 分 治 的 办 法 : 将 个 叶 节 点 的 完 全 二 叉 树 分 解 为 两 个 / 叶 节 点 的 完 成 二 叉 树, 对 这 两 个 子 完 成 二 叉 树 进 行 递 归 布 线, 然 后 将 结 果 合 并 即 可 这 样 分 治 的 结 果 将 形 成 如 图 3-1 所 示 的 布 局 图 3-1 完 全 二 叉 树 在 芯 片 晶 格 里 面 的 递 归 排 列 方 式 该 布 局 的 形 状 是 一 个 正 方 形, 即 w () = h () 正 方 形 的 每 条 边 的 长 度 可 由 下 面 的 递 归 表 达 式 表 示 :

根 据 大 师 解 法, 我 们 获 得 w () = h () = Θ ( 个 对 数 级 的 改 善! 3.8 多 项 式 乘 法 w () = h () = w (/4) + Θ(1) 第 3 章 分 治 与 递 归 43 ) 因 此, 整 个 布 局 所 占 空 间 为 Θ () 这 是 一 本 章 讨 论 的 整 数 的 乘 法 问 题 可 以 扩 展 到 浮 点 数 和 多 项 式 上, 即 两 个 多 项 式 相 乘 也 可 用 通 过 分 治 来 降 低 算 法 的 复 杂 度 但 这 种 分 治 牵 涉 到 多 项 式 的 点 值 表 示 与 傅 里 叶 变 换 有 兴 趣 的 读 者 可 参 阅 文 献 [1] 的 相 关 章 节, 这 里 不 再 赘 述 3.9 分 治 就 在 潜 意 识 深 处 分 治 并 不 是 一 个 特 定 的 算 法, 而 是 一 种 算 法 思 想 这 种 思 想 来 源 于 人 们 偏 向 处 理 简 单 的 事 情, 因 为 简 单 的 东 西 比 复 杂 的 东 西 好 应 付 而 且 现 实 世 界 确 实 由 简 单 的 东 西 构 成 : 如 果 将 物 质 不 断 细 分, 发 现 其 最 后 的 构 成 都 是 一 样 的 因 此, 分 治 策 略 可 以 说 根 植 在 人 们 的 潜 意 识 深 处! 与 分 治 策 略 不 可 分 割 的 一 个 概 念 就 是 递 归 没 有 递 归, 分 治 也 就 无 从 落 地, 而 成 了 空 中 楼 阁 因 此, 如 何 求 解 递 归 就 成 为 分 治 策 略 的 根 基 从 某 种 程 度 上 说, 分 治 与 递 归 互 为 因 果 思 考 题 1. 请 给 出 如 何 将 两 个 位 数 的 乘 法 分 解 为 3 个 / 位 的 乘 法 运 算. 按 照 我 们 的 分 治 方 法, 计 算 一 个 长 度 为 的 数 的 立 方 的 效 率 3. 对 于 表 达 式 T () = 4T (/) +, 有 同 学 按 照 如 下 方 式 证 明 该 递 归 表 达 式 的 解 为 T () = O ( ): 对 k <, 设 T (k) ck, 则 有 T ()=4T (/)+ 4c(/) + = c += O ( ) 证 毕 请 问 该 同 学 的 证 明 有 什 么 问 题 吗? 请 予 以 解 释 4. 平 方 运 算 与 乘 法 运 算 的 不 同 点 是 乘 数 和 被 乘 数 相 同, 这 点 不 同 对 我 们 设 计 算 法 有 何 影 响? 平 方 运 算 能 否 比 普 通 乘 法 运 算 快 呢? 这 里 假 定 所 有 操 作 数 的 长 度 为 位 5. 分 治 策 略 一 定 包 含 递 归 吗? 如 果 是, 请 解 释 如 果 不 是, 给 出 一 个 不 包 含 递 归 的 分 治 例 子, 并 阐 述 这 种 分 治 和 包 含 递 归 的 分 治 的 主 要 不 同 6. 给 定 个 球, 其 中 1 个 球 为 次 品 次 品 从 外 表 上 看 与 正 常 球 一 样, 但 重 量 有 区 别, 它 可 能 比 正 常 球 重, 也 可 能 比 正 常 球 轻 给 你 一 个 天 平, 需 要 称 几 次 就 能 将 次 品 甄 别 出 来?

44 第 一 篇 算 法 基 础 篇 注 意, 你 的 思 路 应 该 比 本 章 开 篇 的 思 路 更 加 高 效 7. 我 们 说 过 分 治 通 常 都 包 含 着 递 归, 但 是 否 递 归 也 通 常 包 含 着 分 治 呢? 为 什 么? 8. 一 次 大 型 派 对 的 最 后 节 目 是 选 出 一 位 幸 运 人 士, 该 人 将 获 得 派 对 组 织 者 准 备 的 一 个 钻 石 戒 指 而 选 择 幸 运 人 士 的 办 法 是 让 所 有 人 员 一 字 排 列, 然 后 从 左 至 右 点 数, 凡 是 奇 数 号 的 全 部 剔 除 对 于 剩 下 的 人 员, 又 从 左 至 右 点 数, 逢 奇 数 号 就 剔 除 如 此 不 断 递 归 下 去, 直 到 只 剩 一 人 为 止 此 人 即 为 幸 运 之 人 请 设 计 一 个 递 归 算 法 计 算 幸 运 之 人 所 在 的 位 置, 并 分 析 该 算 法 的 时 间 效 率 9. 请 给 出 一 个 计 算 整 数 x 和 y 最 小 公 倍 数 的 算 法, 并 分 析 其 时 间 成 本 1. 请 问 第 8 题 里 面 的 策 略 包 含 着 分 治 的 思 想 吗? 为 什 么? 11. 请 问 计 算 第 个 斐 波 那 契 数 F 能 够 在 多 少 时 间 内 完 成? 是 O (lg) 吗? 1. 递 归 在 编 译 器 的 设 计 中 随 处 可 见, 请 举 出 一 个 例 子, 并 说 明 编 译 器 设 计 是 如 何 解 决 此 种 递 归 的 编 译 器 的 递 归 方 法 是 分 治 吗? 为 什 么?