1652286-李辉-第9次算法实现1
需积分: 0 142 浏览量
2022-08-03
23:28:29
上传
评论
收藏 290KB PDF 举报
思路：
题目要求平均等待的时间最短，即时间越短应被计算次数越多，时间越多被计算次数要越少，
所以对服务时间最短的顾客先服务，这是贪心选择策略，做完第一次选择后，原问题 T 变成
了需对 n—1 个顾客服务的新问题 T’，规模一直缩小，符合贪心算法。
时空复杂度分析：
先 将 服 务 时 间 进 行 由 小 到 大 的 排 序 ， 之 后 进 行 时 间 累 加 求 和 ， 时 间 复 杂 度 为
O(nlogn)+O(n)=O(nlogn)
定义了两个向量分别存储每一个顾客等待的时间和每个服务窗口等待时间之和，空间复杂度
为 O(n)
评论0