算法分析与设计之贪心算法.ppt

贪心算法之线段覆盖问题 姓名：moumou 学号：xxxxx 专业：计算机科学与技术 算法思想： 用随机函数获取数轴上所需的点，先将实数轴上的n 个点{x1,x2,x3,…,xn}, xi∈R按照从小到大的顺序排列；用单位长度的线段去覆盖时，按照从左到右的顺序覆盖，且在可以覆盖的情况下，使得线段的右端点尽可能的靠右。 贪心算法之线段覆盖问题 贪心算法之线段覆盖问题 6个特征： n个点都是实数轴上的点； 单位线段是长度为1的点； 随机函数获取轴上点，使数据获取更加方便一点 点按照从小到大的顺排列时，覆盖的时候方便于比较； 要求用的线段数尽可能的少； 单位长度的线段覆盖的点越多，则用的单位线段的数量就越少； 贪心算法核心代码： 贪心算法之线段覆盖问题 冒泡排序核心代码： 贪心算法之线段覆盖问题 测试用例及结果： 实数轴上需要覆盖的点的个数：10 10个点分别为： 00.8702624，0.9256977，0.9739882，1.8285234 2.4306035，3.4615386，3.7497804，4.1673627，4.7247934 用的线段数量为：4 贪心算法之线段覆盖问题 运行结果图： 贪心算法之线段覆盖问题 算法分析： 就该题中的贪心算法的核心代码分析，最好情况下时间复杂度为（n-1），最坏情况下时间复杂度为O（n-1），平均时间复杂度为O（n）。 贪心算法之线段覆盖问题 是否可得到最优解： 因为算法最坏情况下的时间复杂度为O（n-1），而问题的下届的时间复杂度为O（n-1），即求解问题的下届=算法的上届 所以该算法可以得到最优解。 贪心算法之线段覆盖问题