程序javascript的時間複雜度，用於計劃任務

-1

您的研究機構剛剛收到一臺新的超級計算機。它能夠同時處理幾項不同的任務，但前提是它知道每項任務需要多長時間才能得出結果。程序javascript的時間複雜度，用於計劃任務

這臺超級計算機測量時間以時間爲單位，並在以下方式操作：

需要處理的所有任務都放置在隊列中。隊列頂部的任務恰好給定了1個CPU時間單位。如果未完成，則將其放置在隊列的後面。隊列中的任務重新調度由特殊處理單元管理，因此不需要額外的CPU時間。您已將您的任務提交到處理隊列，並且您想了解需要等待多長時間直到結果準備就緒。

給定taskQueue爲一個正整數數組，其中taskQueue [i]表示爲隊列中的第i個任務提供結果所剩餘的CPU時間的時間單位數，以及一個正整數n作爲您的當前索引taskQueue中的任務（從0開始），查找在完成任務之前需要等待的時間單位數。

例

對於TASKQUEUE = [3,1，2]且n = 2時，輸出應該是多任務（TASKQUEUE中，n）= 5 如果我們通過隊列狀態與1個單位時間步驟如下： [3,1,2'] - > [1,2'，2] - > [2'，2] - > [2,1'] - > [1'，1] - > [1] 您的任務標記爲'。對於TASKQUEUE = [1，2，3，1，2]和n = 0時，輸出應該是多任務（TASKQUEUE中，n）= 1 輸入/輸出

[時限] 4000ms（JS） [input] array.integer taskQueue

第ith個整數表示隊列中第i個任務給出結果所剩的CPU時間單位的數量。

保證約束： 1≤taskQueue.length≤105 1≤TASKQUEUE [I]≤109

[輸入]整數n

在TASKQUEUE你的任務的索引（從0開始）。

保證約束： 0≤n < taskQueue.length。

[輸出] integer64

，你需要等待，直到你的任務完成時間單位數。

這是我寫的代碼：

function multitasking(taskQueue, n) { 
let queue = new Queue(taskQueue,n); 
while(queue.data.length) { 
    queue.runTask(); 
} 
return queue.count;

}

function Queue(data,n) { 
this.data = [...data]; 
this.taskIndex = n; 
this.count = 0; 

this.requeue = function() { 
    let firstvalue = this.data[0];   
    if(this.taskIndex) { 
     this.taskIndex--; 
    } else if(!firstvalue) { 
     this.data = [];  
     return;        
    } else { 
     this.taskIndex = this.data.length-1; 
    } 
    if(firstvalue) { 
     this.data.push(firstvalue); 
    } 
    this.data.shift(); 
} 

this.runTask = function() { 
    this.data[0]--; 
    this.count++; 
    this.requeue(); 
}}

這非常適用於大多數情況下。但時間複雜度很高。對於。例如。

多任務（[1000000000,1000000000]，1）這不能解決4000ms以下。任何人都可以幫助我減少時間複雜性？

來源

2017-11-11 Shiva Pandey

你似乎是運行仿真而不是分析。這是基於使用增量運算符將queue.count調整爲1。計算剩餘時間所需的時間將會增加，具體取決於任務完成的時間。

我在分析剩餘時間不通過每一步要做的第一想法如下（未經檢驗，未編碼）：

規範化任務隊列把第n個零基於任務的頭。這將需要（n）個時間單位，因此將總時間設置爲（n）。不要將時間長度爲1的任務之前的任務添加到規範化隊列的末尾。
發現以下小於你的任務要求任務最少的所需時間計數。
如果在步驟2中找到任務，請將其時間乘以任務隊列長度加上總時間，然後從隊列中的所有時間中減去任務時間。刪除從隊列中找到的任務。
如果在任何時候的時間你的任務剩下的就是一個，添加一個總並將其返回。
如果一個任務是在步驟2中發現，重複步驟2
添加剩餘您的任務完成總並返回結果的時間。

更新：

第二個想法將仍是「正常化」的隊列 - 會是什麼樣的隊列樣子n後的時間單位，其中n是在隊列中的任務的位置（它可能是零）？

現在的問題是，是否在循環賽的方式隊列執行其他任務的順序會影響計算時間，你的任務完成？如果不是，您可以將隊列的其餘部分按降序排序，同時將您的任務留在隊列頂部。

如果順序無關緊要，您可以處理從數組末尾開始排序的隊列條目，並且通過維護多個累加器（例如，需要總時間和隊列迭代次數）來計算您所需的時間任務完成而不需要操作隊列的數組結構，甚至不需要數組中的入口值。

更精細的細節還需要進行處理，但是進行這種分析所需的時間應取決於最初的隊列中，而不是剩餘每項任務的時間的長度。

來源

2017-11-11 06:19:08 traktor53

程序javascript的時間複雜度，用於計劃任務

回答

相關問題