南阳理工学院
算法设计与分析报告册
开课学院： 计算机与信息工程学院 实验项目： 贪心算法实验 实验时间： 实验地点： 指导教师： 学生姓名： 学生学号：
专业班级： 18大数据
2024-2024学年第2学期
一、实验目的
1.了解贪心算法思想及基本原理 2.掌握使用贪心算法求解问题的一般特征 3.能够针对实际问题，能够正确选择贪心策略。 4.能够针对选择的贪心策略，证明算法的正确性。 5.能够根据贪心策略，正确编码。
6.能够正确分析算法的时间复杂度和空间复杂度
二、实验平台
1.Windows操作系统或Linux操作系统 2.Python3.x
3.pyCharm或sublime或jupyter notebook
三、实验内容
最优服务次序问题：设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,1≤i≤n。共有s处可以提供此服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小平均等待时间是n个顾客等待服务时间的总和除以n。
四、算法设计
1.问题分析
根据贪心思想，哪位顾客服务所需的时间短，就先服务那个顾客，然后依次类推，每次都是首先服务所需时间短的，这样能保证等待时间最短。
2. 问题建模
输入;集合s={1,2,3,...,n},第i个顾客的服务时间； 输出：第i个顾客的等待时间
目标函数：SUM(每个顾客的等待时间）/总顾客的数，得到平均等待时间
3.算法描述
首先保存每位顾客的服务时间到数组，然后把服务时间使用冒泡排序按照从小到大排序，然后遍历数组，服务时间最小的先服务，然后其次被服务的顾客的等待时间为（上一位顾客的服务时间和自己的被服务时间）最后求出总的服务时间在除以总顾客数得到最小平均等待时间。
五、算法源码
def waitime(n):
a=[0 for i in range(0,n)]#定义一个数组并将n个服务时间存进数组a for i in range(0,len(a)):
a[i]=int(input((\请输入顾客需要的服务时间:\)))
for i in range(0, len(a) - 1): # 冒泡排序，将这n个服务时间从小到大排序 for j in range(0, len(a) - i - 1): if (a[j] > a[j + 1]):
a[j], a[j + 1] = a[j + 1], a[j] sum=a[0]#排完序后第一个最先开始 for i in range(1,len(a)): a[i]=a[i]+a[i-1] sum=sum+a[i]
time=sum/n#求出最小平均等待时间 print(\最小平均等待时间是：\,time) if __name__ == \:
n=int(input((\请输入顾客个数：\))) waitime(n)
六、测试数据
请输入顾客个数：4
分别为：2 3 5 1
最小平均等待时间是： 5.25
七、程序运行结果（要求：截图说明算法运行的结果）
八、算法分析（分析算法的时间复杂度和空间复杂度）
时间复杂度：程序进行了一次排序（O(nlogn)）和循环（O(n)），故时间复杂度为O(nlogn)；
空间复杂度：程序定义了一个一维数组（lengh_n[n]）用于存放每个程序的大小，故时间复杂度为O(n)。
九、 实验总结
通过这次实验，我对贪心算法有了更深的了解，对于pthon语言的认识也更加深刻了，巩固了以往所学的知识，对于冒泡排序的运用也更熟练了，贪心就是要用最小的付出，得到最大的收益，这对解决很多问题都有帮助。了解了贪心算法思想及基本原理，学会使用贪心算法求解问题的一般特征，能够针对实际问题，能够正确选择贪心策略。
贪心算法实验python
