绝妙的算法——最大子序列和问题.doc

1、摘要 本 文 分 析 并 演 示 最 大 子 序 列 和 问 题 的 几 种 算 法 ， 它 们 都 能 解 决 问 题 ， 但 是 时 间 复 杂 度 却 大 相 径庭 ， 最 后 将 逐 步 降 低 至 线 性 。算法 子序列和问 题 的 引 入给 定 （ 可 能 有 负 数 ） 整 数 序 列 A1, A2, A3., An， 求 这 个 序 列 中 子 序 列 和 的 最 大值 。 （ 为 方 便 起 见 ， 如 果 所 有 整 数 均 为 负 数 ， 则 最 大 子 序 列 和 为 0） 。 例 如 ： 输 入 整数 序 列 ： -2, 11, 8, -4, -1, 16, 5, 0

2、， 则 输 出 答 案 为 35， 即 从 A2 A6。这 个 问 题 之 所 以 有 吸 引 力 ， 主 要 是 因 为 存 在 求 解 它 的 很 多 算 法 ， 而 这 些 算 法 的 性 能差 异 又 很 大 。 这 些 算 法 ， 对 于 少 量 的 输 入 差 别 都 不 大 ， 几 个 算 法 都 能 在 瞬 间 完 成 ， 这 时若 花 费 大 量 的 努 力 去 设 计 聪 明 的 算 法 恐 怕 就 不 太 值 得 了 ； 但 是 如 果 对 于 大 量 的 输 入 ， 想要 更 快 的 获 取 处 理 结 果 ， 那 么 设 计 精 良 的 算 法 显 得 很 有 必 要

3、 。切 入 正 题下 面 先 提 供 一 个 设 计 最 不 耗 时 间 的 算 法 ， 此 算 法 很 容 易 设 计 ， 也 很 容 易 理 解 ， 但 对于 大 量 的 输 入 而 言 ， 效 率 太 低 ：算 法 一 ：public static int maxSubsequenceSum(int a) int maxSum = 0;for(int i=0; i maxSum)maxSum = thisSum;return maxSum;上 述 设 计 很 容 易 理 解 ， 它 只 是 穷 举 各 种 可 能 的 结 果 ， 最 后 得 出 最 大 的 子 序 列 和 。 毫 无 疑

4、 问 ， 这 个算 法 能 够 正 确 的 得 出 和 ， 但 是 如 果 还 要 得 出 是 哪 个 子 序 列 ， 那 么 这 个 算 法 还 需 要 添 加 一 些 额 外 的 代 码 。现 在 来 分 析 以 下 这 个 算 法 的 时 间 复 杂 度 。 运 行 时 间 的 多 少 ， 完 全 取 决 于 第 6、 7 行 ， 它 们 由 一个 含 有 三 重 嵌 套 for 循 环 中 的 O(1)语 句 组 成 ： 第 3 行 上 的 循 环 大 小 为 N， 第 4 行 循 环 大 小 为 N-i， 它 可 能 很 小 ， 但 也 可 能 是 N。 我 们 在 判 断 时 间

5、复 杂 度 的 时 候 必 须 取 最 坏 的 情 况 。 第 6 行 循 环 大小 为 j-i+1， 我 们 也 要 假 设 它 的 大 小 为 N。 因 此 总 数 为 O(1*N*N*N)=O(N3)。 第 2 行 的 总 开 销为 O(1)， 第 8、 9 行 的 总 开 销 为 O(N2)， 因 为 它 们 只 是 两 层 循 环 内 部 的 简 单 表 达 式 。我 们 可 以 通 过 拆 除 一 个 for 循 环 来 避 免 3 次 的 运 行 时 间 。 不 过 这 不 总 是 可 能 的 ， 在 这 种 情 况 下 ，算 法 中 出 现 大 量 不 必 要 的 计 算 。

6、纠 正 这 种 低 效 率 的 改 进 算 法 可 以 通 过 观 察 Sum(AiAj) = Aj + Sum(AiAj-1)而 看 出 ， 因 此 算 法 1 中 第 6、 7 行 上 的 计 算 过 分 的 耗 费 了 。 下 面 是 在 算 法 一 的 基 础上 改 进 的 一 种 算 法 ：算 法 二 ：public static int maxSubsequenceSum(int a) int maxSum = 0;for(int i=0; i maxSum)maxSum = thisSum;return maxSum;对 于 此 算 法 ， 时 间 复 杂 度 显 然 是 O(N

7、2)， 对 它 的 分 析 甚 至 比 前 面 的 分 析 还 要 简 单 ，就 是 直 接 使 用 穷 举 法 把 序 列 中 i 后 面 的 每 个 值 相 加 ， 如 果 发 现 有 比 maxSum 大 的 ，则 更 新 maxSum 的 值 。对 于 这 个 问 题 ， 有 一 个 递 归 和 相 对 复 杂 的 O(NlogN)解 法 ， 我 们 现 在 就 来 描 述 它 。要 是 真 的 没 有 出 现 O(N)（ 线 性 的 ） 解 法 ， 这 个 算 法 就 会 是 体 现 递 归 为 例 的 极 好 的 范 例了 。 该 方 法 采 用 一 种 “分 治 ”策 略 。 其

8、 想 法 就 是 吧 问 题 分 成 两 个 大 致 相 等 的 子 问 题 ，然 后 递 归 地 对 它 们 求 解 ， 这 是 “分 ”的 阶 段 。 “治 ”阶 段 就 是 将 两 个 子 问 题 的 解 修 补到 一 起 并 可 能 再 做 些 少 量 的 附 加 工 作 ， 最 后 得 到 整 个 问 题 的 解 。在 我 们 的 例 子 中 ， 最 大 子 序 列 的 和 只 可 能 出 现 在 3 个 地 方 ：1.出 现 在 输 入 数 据 的 左 半 部 分2.3.出 现 在 输 入 数 据 的 右 半 部 分4.5.跨 越 输 入 数 据 的 中 部 而 位 于 左 右 两

9、 个 部 分6.前 两 种 情 况 可 以 递 归 求 解 ， 第 三 种 情 况 的 最 大 和 可 以 通 过 求 出 前 半 部 分 （ 包 含 前 半部 分 的 最 后 一 个 元 素 ） 的 最 大 和 以 及 后 半 部 分 （ 包 括 后 半 部 分 的 第 一 个 元 素 ） 的 最 大 和 ，再 将 二 者 相 加 得 到 。 作 为 例 子 ， 考 虑 以 下 输 入 ：-前半部分 后半部分 -2, 11, 8, -4, -1, 16, 5, 0 -其 中 ， 前 半 部 分 的 最 大 子 序 列 和 为 19（ A2A3） ， 而 后 半 部 分 的 最 大 子 序 列

10、 和 为21（ A6 A7） 。 前 半 部 分 包 含 其 最 后 一 个 元 素 的 最 大 和 是 15（ A2 A4） ， 后 半 部 分 包 含 第 一 个元 素 的 最 大 和 是 20（ A5 A7） 。 因 此 ， 跨 越 这 两 部 分 的 这 个 子 序 列 才 是 拥 有 最 大 和 的 子 序 列 ， 和为 15+20=35（ A2 A7） 。 于 是 出 现 了 下 面 这 种 算 法 ：算 法 三 ：public static int maxSubsequenceSum(int a, int left, int right) if(left = right) /Ba

11、se caseif(aleft 0) return aleft; else return 0; /保证最小值为 0int center = (left+right)/2;int maxLeftSum = maxSubsequenceSum(a, left, center); /递归调用，求左部分的最大和int maxRightSum = maxSubsequenceSum(a, center+1, right);/递归调用，求右部分的最大和int leftBorderSum = 0, maxLeftBorderSum = 0;/定义左边界子序列的和for(int i=center; i=lef

12、t; i-) leftBorderSum += ai;if(leftBorderSum maxLeftBorderSum) maxLeftBorderSum = leftBorderSum;int rightBorderSum = 0, maxRightBorderSum = 0;/定义左边界子序列的和for(int i=center+1; i maxRightBorderSum) maxRightBorderSum = rightBorderSum;/选出这三者中的最大值并返回（max3(int a, int b, int c)的实现没有给出）return max3(maxLeftSum,

13、maxRightSum, maxLeftBorderSum + maxRightBorderSum);有 必 要 对 算 法 三 的 程 序 进 行 一 些 说 明 。 递 归 过 程 调 用 的 一 般 形 式 是 传 递 输 入 的 数 组和 左 右 边 界 ， 它 们 界 定 了 数 组 要 被 处 理 的 部 分 。 第 2 8 行 处 理 基 准 情 况 ， 让 递 归 调用 有 退 出 的 机 会 。 如 果 left=right， 那 么 只 有 一 个 元 素 ， 并 且 当 该 元 素 非 负 时 ， 它就 是 最 大 子 序 列 。 第 11、 12 行 执 行 两 个 递

14、 归 调 用 。 我 们 可 以 看 到 ， 递 归 调 用 总 是 对小 于 原 问 题 的 问 题 进 行 ， 不 过 程 序 中 的 小 扰 动 有 可 能 破 坏 这 个 特 性 。 14 20 行 ，22 28 行 分 界 处 左 右 两 边 的 最 大 子 序 列 和 ， 这 两 个 值 的 和 就 有 可 能 是 整 个 序 列 中 的 最大 子 序 列 和 。 第 31 行 调 用 max3 方 法 ， 求 出 这 三 种 情 况 下 的 最 大 值 ， 该 值 即 为 整 个序 列 的 最 大 子 序 列 和 。显 然 ， 算 法 三 需 要 比 设 计 前 两 种 算 法

15、付 出 更 多 的 编 程 努 力 ， 看 上 去 前 面 两 种 算 法 的代 码 量 要 比 算 法 三 少 许 多 ， 然 而 ， 程 序 短 并 不 意 味 着 程 序 好 。 测 试 表 明 ， 除 较 小 的 输 入量 外 ， 算 法 三 比 前 两 个 算 法 明 显 要 快 。 现 在 来 分 析 以 下 算 法 三 的 时 间 复 杂 度 。令 T(N)是 求 解 大 小 为 N 的 最 大 子 序 列 和 问 题 所 花 费 的 时 间 。 如 果 N=1， 则 算 法3 执 行 程 序 第 2 8 行 花 费 某 个 常 数 时 间 ， 我 们 称 之 为 一 个 时 间

16、 单 位 。 于 是 T(1)=1， 否 则 ， 程 序 必 须 执 行 两 个 递 归 调 用 ， 即 在 14 28 行 之 间 的 两 个 for 循 环 以 及几 个 小 的 簿 记 量 ， 如 10、 14 行 。 这 两 个 for 循 环 总 共 接 触 到 A1An 中 的 每 个 元 素 ，而 在 循 环 内 部 的 工 作 量 是 常 量 ， 于 是 14 28 行 花 费 的 时 间 为 O(N)。 从2 10、 14、 22 和 31 行 上 的 程 序 的 工 作 量 是 常 量 ， 从 而 与 O(N)相 比 可 以 忽 略 。 其余 就 剩 下 11 12 行 上

17、 运 行 的 工 作 。 这 两 行 求 解 大 小 为 N/2 的 子 序 列 问 题 （ 假 设 N为 偶 数 ） 。 因 此 ， 这 两 行 每 行 花 费 T(N/2)个 时 间 单 元 ， 共 花 费 2T(N/2)个 时 间 单 元 。因 此 ， 算 法 三 花 费 的 总 时 间 为 2T(N/2)+O(N)。 于 是 我 们 得 到 方 程 组 ：T(1) = 1T(N) = 2T(N/2) + O(N)为 了 简 化 计 算 ， 我 们 可 以 用 N 代 替 上 面 方 程 中 的 O(N)项 ； 由 于 T(N)最 终 还 是 要 用 大 O 表 示 ，因 此 这 么 做

18、 并 不 影 响 答 案 。 现 在 ， 如 果 T(N) = 2T(N/2) + N， 且 T(1) = 1， 那 么 T(2) = 4 = 2*2； T(4) = 12 = 4*3； T(8) = 32 = 8*4； T(16) = 80 = 16*5。 用 数 学 归 纳 法 可 以 证 明 若N=2k， 那 么 T(N) = 2k * (k+1) = N * (k+1) = N(logN + 1) = NlogN + N = O(NlogN)。即 算 法 三 的 时 间 复 杂 度 为 O(NlogN)， 这 明 显 小 于 算 法 二 的 复 杂 度 O(N2)， 因 此 算 法 三

19、 会 更 快 的得 出 结 果 。这 个 分 析 假 设 N 是 偶 数 ， 否 则 N/2 就 不 确 定 了 。 通 过 该 分 析 的 递 归 性 质 可 知 ， 实 际 上 只 有 当N 是 2 的 幂 时 结 果 才 是 合 理 的 ， 否 则 我 们 最 终 要 得 到 大 小 不 是 偶 数 的 子 问 题 ， 方 程 就 是 无 效 的 了 。当 N 不 是 2 的 幂 时 ， 我 们 多 少 需 要 更 加 复 杂 一 些 的 分 析 ， 但 是 大 O 的 结 果 还 是 不 变 的 。更 优 秀 的 算 法虽 然 算 法 三 已 经 足 够 优 秀 ， 将 时 间 复 杂

20、 度 由 O(N2)降 低 为 O(NlogN)， 但 是 ， 这 并 不 是 最 优 秀的 ， 下 面 介 绍 针 对 这 个 问 题 更 优 秀 的 解 法 。算 法 四 ：public static int maxSubsequenceSum(int a) int maxSum = 0, thisSum = 0;for(int i=0; i maxSum)maxSum = thisSum;else if(thisSum 0)thisSum = 0;return maxSum;很 显 然 ， 此 算 法 的 时 间 复 杂 度 为 O(N)， 这 小 于 算 法 三 中 的 时 间 复 杂

21、 度 O(NlogN)， 因 此 ， 此算 法 比 算 法 三 更 快 ！ 方 法 固 然 已 给 出 ， 但 是 要 明 白 为 什 么 此 方 法 能 用 ， 还 需 多 加 思 考 。在 算 法 一 和 算 法 二 中 ， i 代 表 子 序 列 的 起 点 ， j 代 表 子 序 列 的 终 点 。 碰 巧 的 是 ， 我 们 不 需 要 知 道具 体 最 佳 的 子 序 列 在 哪 里 ， 那 么 i 的 使 用 可 以 从 程 序 上 被 优 化 ， 因 此 在 设 计 算 法 的 时 候 假 设 i 是必 需 的 ， 而 且 我 们 想 改 进 算 法 二 。 一 个 结 论 是

22、 ： 如 果 ai是 负 数 ， 那 么 它 不 可 能 代 表 最 优 序 列 的 起点 ， 因 为 任 何 包 含 ai的 作 为 起 点 的 子 序 列 都 可 以 通 过 使 用 ai+1作 为 起 点 得 到 改 进 。 类 似 的 ，任 何 负 的 子 序 列 也 不 可 能 是 最 优 子 序 列 的 前 缀 （ 原 理 相 同 ） 。 如 果 在 内 循 环 中 检 测 到 从 ai到 aj的子 序 列 的 和 是 负 数 ， 那 么 可 以 向 后 推 进 i。 关 键 的 结 论 是 ： 我 们 不 仅 能 够 把 i 推 进 到 i+1， 而 且实 际 上 我 们 还 可

23、 以 把 它 一 直 推 进 到 j+1。 为 了 看 清 楚 这 一 点 ， 我 们 令 p 为 i+1 和 j 之 间 的 任意 一 下 标 。 开 始 于 下 标 p 的 任 意 子 序 列 都 不 大 于 在 下 标 i 开 始 并 包 含 从 ai 到 ap-1 的 子 序列 的 对 应 的 子 序 列 ， 因 为 后 面 这 个 子 序 列 不 是 负 的 （ 即 j 是 使 得 从 下 标 i 开 始 ， 其 值 成 为 负 值 的序 列 的 第 一 个 下 标 ） 。 因 此 ， 把 i 推 进 到 j+1 是 没 有 风 险 的 ： 我 们 一 个 最 优 解 也 不 会 错

24、 过 。这 个 算 法 是 许 多 聪 明 算 法 的 典 型 ： 运 行 时 间 是 明 显 的 ， 但 正 确 性 却 不 那 么 容 易 就 能 看 出 来 。 对 于这 些 算 法 ， 正 式 的 正 确 性 证 明 （ 比 上 面 分 析 更 加 正 式 ） 几 乎 总 是 需 要 的 ； 然 而 ， 及 时 到 那 时 ， 许 多 人仍 然 还 是 不 信 服 。 此 外 ， 许 多 这 类 算 法 需 要 更 有 技 巧 的 编 程 ， 这 导 致 更 长 的 开 发 过 程 。 不 过 ， 当 这 些算 法 正 常 工 作 时 ， 它 们 运 行 得 很 快 ！ 而 我 们 将

25、 它 们 和 一 个 低 效 但 容 易 实 现 的 蛮 力 算 法 通 过 小 规 模 的 输入 进 行 比 较 可 以 测 试 到 大 部 分 的 程 序 原 理 。该 算 法 的 一 个 附 带 优 点 是 ： 它 值 对 数 据 进 行 一 次 扫 描 ， 一 旦 ai被 读 入 并 处 理 ， 它 就 不 再 需 要被 记 忆 。 因 此 ， 如 果 数 组 在 磁 盘 上 活 通 过 网 络 传 送 ， 那 么 它 就 可 以 被 按 顺 序 读 入 ， 在 主 存 中 不 必 存 储改 数 组 的 任 何 部 分 。 不 仅 如 此 ， 在 任 意 时 刻 ， 算 法 都 能 对 它 已 经 读 入 的 数 据 给 出 子 序 列 问 题 的 正 确 答案 （ 其 他 算 法 不 具 备 这 个 特 性 ） 。 具 有 这 种 特 性 的 算 法 叫 做 “联 机 算 法 ”。 仅 需 要 常 量 空 间 并 以线 性 时 间 运 行 的 联 机 算 法 几 乎 是 完 美 的 算 法 。