算法分析与设计之贪心算法ppt课件.ppt_第1页
算法分析与设计之贪心算法ppt课件.ppt_第2页
算法分析与设计之贪心算法ppt课件.ppt_第3页
算法分析与设计之贪心算法ppt课件.ppt_第4页
算法分析与设计之贪心算法ppt课件.ppt_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

贪心算法之线段覆盖问题 姓名 moumou学号 xxxxx专业 计算机科学与技术 算法思想 用随机函数获取数轴上所需的点 先将实数轴上的n个点 x1 x2 x3 xn xi R按照从小到大的顺序排列 用单位长度的线段去覆盖时 按照从左到右的顺序覆盖 且在可以覆盖的情况下 使得线段的右端点尽可能的靠右 贪心算法之线段覆盖问题 贪心算法之线段覆盖问题 6个特征 n个点都是实数轴上的点 单位线段是长度为1的点 随机函数获取轴上点 使数据获取更加方便一点点按照从小到大的顺排列时 覆盖的时候方便于比较 要求用的线段数尽可能的少 单位长度的线段覆盖的点越多 则用的单位线段的数量就越少 贪心算法核心代码 贪心算法之线段覆盖问题 冒泡排序核心代码 贪心算法之线段覆盖问题 测试用例及结果 实数轴上需要覆盖的点的个数 1010个点分别为 0 25740233 0 8702624 0 9256977 0 9739882 1 82852342 4306035 3 4615386 3 7497804 4 1673627 4 7247934用的线段数量为 4 贪心算法之线段覆盖问题 运行结果图 贪心算法之线段覆盖问题 算法分析 就该题中的贪心算法的核心代码分析 最好情况下时间复杂度为 n 1 最坏情况下时间复杂度为O n 1 平均时间复杂度为O n 贪心算法之线段覆盖问题 是否可得到最优解 因为算法最坏情况下的时间复杂度为O n 1 而问题的下届的时间复杂度为O n 1 即求解问题的下届 算法的上届所以该算法可以得到最优解 贪心算法之线段覆盖问题
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论