数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究查找给定进程的完成处理时间
给定 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] 更新为当前的 time 值。
将 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
上述算法的时间复杂度，其中 N 是进程总数，为 O(N2)。这是因为我们在循环的每次迭代中都扫描整个 arr1[] 数组以确定在临界区需要花费多少时间。这种扫描发生 N 次，时间复杂度为 O(N)，从而产生 O(N2) 的时间复杂度。
该算法的空间复杂度为 O(N)，因为我们使用了一个大小为 N 的数组来存储每个进程完成处理所需的时间。算法中的其他变量（time、minArr1 和 i）不会增加总空间复杂度，因为它们都需要固定的空间。
优化方法
可以通过使用优先级队列（或最小堆）而不是扫描整个 arr1[] 数组来查找在临界区花费的最小时间，从而优化算法的时间复杂度。
我们可以创建一个最小堆来存储每个进程在临界区花费的时间。然后，我们重复地从堆中提取在临界区花费的最小时间，将其添加到总时间中，并计算该进程的完成时间。我们更新该进程的完成时间并将其重新插入堆中。我们重复此过程，直到堆为空。
使用堆允许我们在 O(log N) 时间内找到在临界区花费的最小时间，而不是 O(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，以防止它们在循环的下一次迭代中被考虑。
将所有剩余的 arr1[] 条目添加到队列中，除了值为 Integer.MAX_VALUE 的条目。
在 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
69 次查看
