首页 > 代码库 > 【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 }
View Code

 

【ZX笔试】短作业优先算法