資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
