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

《算法分析与设计之贪心算法.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计之贪心算法.ppt（10页珍藏版）》请在三一办公上搜索。

1、贪心算法之线段覆盖问题,姓名：moumou学号：xxxxx专业：计算机科学与技术,算法思想：用随机函数获取数轴上所需的点，先将实数轴上的n 个点x1,x2,x3,xn,xiR按照从小到大的顺序排列；用单位长度的线段去覆盖时，按照从左到右的顺序覆盖，且在可以覆盖的情况下，使得线段的右端点尽可能的靠右。,贪心算法之线段覆盖问题,贪心算法之线段覆盖问题,6个特征：n个点都是实数轴上的点；单位线段是长度为1的点；随机函数获取轴上点，使数据获取更加方便一点点按照从小到大的顺排列时，覆盖的时候方便于比较；要求用的线段数尽可能的少；单位长度的线段覆盖的点越多，则用的单位线段的数量就越少；,贪心算法核心代码：

2、,贪心算法之线段覆盖问题,冒泡排序核心代码：,贪心算法之线段覆盖问题,测试用例及结果：实数轴上需要覆盖的点的个数：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），即求解问题的下届=算法的上届所以该算法可以得到最优解。,贪心算法之线段覆盖问题,谢谢！,