极客笔记Java 找到给定进程的处理时间
给定N个进程和两个大小为N的数组arr1[]和arr2[]。进程在关键部分的时间记录在arr1[]中，离开关键部分后的处理完成时间记录在arr2中。目标是确定每个进程在任何给定顺序下的处理时间（包括关键部分内外）。
输入输出场景
假设我们有以下3个数组
输入
N = 3, arr1[] = {1, 4, 3}, arr2[] = {2, 3, 1}
输出
9
- 第一个进程在时间0到达临界区。在临界区的工作在1个时间单位后完成，并在临界区外花费2个时间单位。因此，第一个进程完成的总时间是3个单位。
-
第二个进程在1个时间单位后进入临界区，并在第5个单位后退出临界区。在临界区外花费3个时间单位后，任务最终在第8个时间单位完成。
-
第三个进程在5个时间单位后进入临界区，并在第8个单位后离开。然后在临界区外再花费1个时间单位，从所有进程开始计算完成时间为第9个单位。因此，总共花费的时间是9个单位。
步骤
我们需要考虑每个进程在临界区中花费的时间以及离开临界区后完成处理所需的时间，以计算所有进程所需的总时间。要确定花费的总时间，我们可以使用以下算法：
- 将变量’time’初始化为0，它将存储总时间。
-
创建一个大小为N的新数组’finishTime[]’，它将存储每个进程完成处理的时间。
-
将’finishTime[]’的所有元素初始化为0。
-
找到在临界区中花费时间最少的进程，并让它处理i。
-
将arr1[i]添加到time中，它是进程i完成临界区任务所需的时间。
-
将arr2[i]添加到time中，它是进程i在离开临界区后完成处理所需的时间。
-
将finishTime[i]更新为当前的时间值。
-
将arr1[i]和arr2[i]设置为无穷大，以标记进程i已完成。
-
重复步骤4-8，直到所有进程都已完成。
找到’finishTime[]’数组中的最大值，它将是所有进程花费的总时间。
Java实现
这是相同的Java实现
示例
public class Demo{
public static int total_time(int N, int[] arr1, int[] arr2) {
int time = 0;
int[] finishTime = new int[N];
while (true) {
int minArr1 = Integer.MAX_VALUE;
int i = -1;
for (int j = 0; j < N; j++) {
if (arr1[j] < minArr1) {
minArr1 = arr1[j];
i = j;
}
}
if (i == -1) {
break;
}
time += arr1[i] + arr2[i];
finishTime[i] = time;
arr1[i] = Integer.MAX_VALUE;
arr2[i] = Integer.MAX_VALUE;
}
int maxFinishTime = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
if (finishTime[i] > maxFinishTime) {
maxFinishTime = finishTime[i];
}
}
return maxFinishTime;
}
public static void main(String args[]){
int N = 3;
int[] arr1 = {1, 4, 3};
int[] arr2 = {2, 3, 1};
System.out.println(total_time(N, arr1, arr2));
}
}
输出
14
以上算法的时间复杂度是O(N^2)，其中N是进程的总数，这是因为我们在每次循环的迭代中扫描整个arr1[]数组来决定在重要区域中需要花费多少时间。这个扫描在O(N)时间内进行N次，导致时间复杂度为O(N^2)。
该技术具有O(N)的空间复杂度，因为我们使用一个大小为N的数组来存储每个操作完成所需的时间。算法中的其他变量（时间、minArr1和i）不会增加总体空间的复杂度，因为它们都需要固定的空间。
优化的方法
通过使用优先队列（或最小堆）而不是扫描整个arr1[]数组来找出在关键区域中花费的最小时间，可以优化算法的时间复杂度。
我们可以创建一个最小堆来存储每个进程在关键区域中花费的时间。然后我们重复地从堆中提取在关键区域中花费的最小时间，将其添加到总时间中，并计算该进程的完成时间。我们更新该进程的完成时间并将其插入堆中。我们重复此过程直到堆为空。
使用堆能够找到在关键区域中花费的最小时间，并将时间复杂度从O(N)降低到O(log N)，从而减少算法的总体时间复杂度为O(N log N)。
算法
以下是优化算法的详细步骤：
- 创建一个整数变量time，并将其初始化为0。该变量将跟踪所有进程所花费的总时间。
-
创建大小为N的整数数组finishTime，并将其所有元素初始化为0。该数组将存储每个进程的完成时间。
-
创建一个PriorityQueue对象pq来存储每个进程在关键区域中花费的时间。将arr1[]的所有元素添加到队列中。
-
当队列不为空时，执行以下操作：
- 使用pq.remove()方法从队列中移除最小的元素，并将其存储在变量minArr1中。
-
在arr1[]中找到具有值minArr1的元素的索引i。我们可以通过线性扫描arr1[]并找到第一个与minArr1匹配的元素来实现。
-
将minArr1和进程i的arr2[]的相应值添加到time变量中。这给出了进程i的总时间。
-
将进程i的总时间存储在finishTime[i]中。
-
将arr1[i]和arr2[i]设置为Integer.MAX_VALUE，以防止它们在下一个循环迭代中被考虑。
-
将除了具有Integer.MAX_VALUE的整数值的所有剩余的arr1[]条目添加到队列中。
-
找出finishTime[]数组中的最大值并返回。这给出了所有进程完成处理所花费的总时间。
这种技术的主要改进是使用优先队列来确定在O(log N)的时间内最小化在关键部分的时间，而不必在O(N)的时间内扫描整个arr1[]数组。这将算法的总体时间复杂度降低为O(N log N)。
Java实现
这是相同算法的Java实现。
示例
import java.util.PriorityQueue;
public class Demo{
public static int total_time(int N, int[] arr1, int[] arr2) {
int time = 0;
int[] finishTime = new int[N];
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
pq.add(arr1[i]);
}
while (!pq.isEmpty()) {
int minArr1 = pq.remove();
int i = -1;
for (int j = 0; j < N; j++) {
if (arr1[j] == minArr1) {
i = j;
break;
}
}
if( i!= -1){
time += minArr1 + arr2[i];
finishTime[i] = time;
arr1[i] = Integer.MAX_VALUE;
arr2[i] = Integer.MAX_VALUE;
for (int j = 0; j < N; j++) {
if (arr1[j] != Integer.MAX_VALUE) {
pq.add(arr1[j]);
}
}
}
}
int maxFinishTime = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
if (finishTime[i] > maxFinishTime) {
maxFinishTime = finishTime[i];
}
}
return maxFinishTime;
}
public static void main(String args[]){
int N = 3;
int[] arr1 = {1, 4, 3};
int[] arr2 = {2, 3, 1};
System.out.println(total_time(N, arr1, arr2));
}
}
输出
14