电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

绝妙的算法——最大子序列和问题VIP免费

绝妙的算法——最大子序列和问题_第1页
1/8
绝妙的算法——最大子序列和问题_第2页
2/8
绝妙的算法——最大子序列和问题_第3页
3/8
本 文 分 析 并 演 示 最 大 子 序 列 和 问 题 的 几 种 算 法 , 它 们 都 能 解 决 问 题 , 但 是 时 间 复 杂 度 却 大相 径 庭 , 最 后 将 逐 步 降 低 至 线 性 。 算 法 子 序 列 和 问 题 的 引 入 给定(可能 有负数)整数序 列A1, A2, A3..., An, 求这个序 列 中子 序 列 和 的 最 大值。(为方便起见, 如果所有整数均为负数, 则最 大 子 序 列 和 为 0)。例如:输入整数序 列 : -2, 11, 8, -4, -1, 16, 5, 0, 则输出答案为 35, 即从 A2~A6。 这个问 题 之所以有吸引力, 主要是 因为存在求解 它 的 很多算 法 , 而这些算 法 的 性 能差异又很大 。这些算 法 , 对于少量的 输入差别都 不大 , 几 个算 法 都 能 在瞬间 完成, 这时 若花费大 量的 努力去设计聪明的 算 法 恐怕就不太值得了;但 是 如果对于大 量的 输入, 想要更快的 获取处理结果, 那么设计精良的 算 法 显得很有必要。 切入正题 下面先提供一个设计最 不耗时 间 的 算 法 , 此算 法 很容易设计, 也很容易理解 , 但 对于大 量的 输入而言, 效率太低 : 算 法 一: public static int maxSubsequenceSum(int[] a) { int maxSum = 0; for(int i=0; i maxSum) maxSum = thisSum; } } return maxSum; } 上 述 设 计 很 容 易 理 解 , 它 只 是 穷 举 各 种 可 能 的 结 果 , 最 后 得 出 最 大 的 子 序 列 和 。 毫 无 疑 问 , 这个 算 法 能 够 正 确 的 得 出 和 , 但 是 如 果 还 要 得 出 是 哪 个 子 序 列 , 那 么 这 个 算 法 还 需 要 添 加 一 些 额 外的 代 码 。 现 在 来 分 析 以 下 这 个 算 法 的 时 间 复 杂 度 。 运 行 时 间 的 多 少 , 完 全 取 决 于 第6、7 行 , 它 们由一个 含有三重嵌套 for 循环中的O(1)语句组成:第3 行 上 的 循环大 小为 N...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

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

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部