首页 > 代码库 > 【ZX笔试】短作业优先算法
【ZX笔试】短作业优先算法
时间复杂度为O(n*n),空间复杂度为O(n)的解法
1 // ShortJobFirst.cpp : 定义控制台应用程序的入口点。 2 // 3 4 #include "stdafx.h" 5 #include <iostream> 6 #include <vector> 7 8 using namespace std; 9 10 /*11 每一步都计算当前时间和总的等待时间,根据当前时间(cpu_time)找到已经就绪的作业下标,12 保存到vec_ready中,遍历vec_ready,时间最小的为下一个作业13 */14 float waitTimeSJF(int* requestTimes,int* durations,int len)15 {16 int cpu_time = 0;17 float waitTime = 0.0;18 19 vector<int> vec_flag;20 vec_flag.resize(len);21 for(int i = 0 ; i < len; i++)//用于标记已完成作业22 vec_flag[i] = 0;23 24 vector<int> vec_ready(len);//保存就绪作业的下标、25 int vec_ready_num = 0;26 27 int cur = 0;28 int next = 0;29 int minNum = 0x7FFFFFFF;30 for(int i = 0; i < len ;i++)31 {32 waitTime += cpu_time - requestTimes[cur];33 cpu_time += durations[cur];34 vec_flag[cur] = 1;35 36 vec_ready_num = 0;37 for(int j= 0;j < len; j++)38 {39 if(vec_flag[j] == 0 && requestTimes[j] < cpu_time)40 vec_ready[vec_ready_num++] = j;41 }42 43 minNum = 0x7FFFFFFF;44 for(int k = 0; k < vec_ready_num;k++)//找到最小的请求时间45 {46 if(durations[vec_ready[k]] < minNum)47 {48 minNum = durations[vec_ready[k]];49 next = vec_ready[k];50 } 51 }52 cur = next;53 }54 return waitTime/len;55 }56 57 int _tmain(int argc, _TCHAR* argv[])58 {59 int requestTimes[4] = {0,2,4,5};60 int durations[4] = {7,4,1,4};61 int len = 4;62 cout<<waitTimeSJF(requestTimes,durations,len)<<endl;63 system("pause");64 return 0;65 }
【ZX笔试】短作业优先算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。