程序javascript的时间复杂度，用于计划任务

问题描述：

您的研究机构刚刚收到一台新的超级计算机。它能够同时处理几项不同的任务，但前提是它知道每项任务需要多长时间才能得出结果。程序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以下。任何人都可以帮助我减少时间复杂性？

答

你似乎是运行仿真而不是分析。这是基于使用增量运算符将queue.count调整为1。计算剩余时间所需的时间将会增加，具体取决于任务完成的时间。

我在分析剩余时间不通过每一步要做的第一想法如下（未经检验，未编码）：

规范化任务队列把第n个零基于任务的头。这将需要（n）个时间单位，因此将总时间设置为（n）。不要将时间长度为1的任务之前的任务添加到规范化队列的末尾。
发现以下小于你的任务要求任务最少的所需时间计数。
如果在步骤2中找到任务，请将其时间乘以任务队列长度加上总时间，然后从队列中的所有时间中减去任务时间。删除从队列中找到的任务。
如果在任何时候的时间你的任务剩下的就是一个，添加一个总并将其返回。
如果一个任务是在步骤2中发现，重复步骤2
添加剩余您的任务完成总并返回结果的时间。

更新：

第二个想法将仍是“正常化”的队列 - 会是什么样的队列样子n后的时间单位，其中n是在队列中的任务的位置（它可能是零）？

现在的问题是，是否在循环赛的方式队列执行其他任务的顺序会影响计算时间，你的任务完成？如果不是，您可以将队列的其余部分按降序排序，同时将您的任务留在队列顶部。

如果顺序无关紧要，您可以处理从数组末尾开始排序的队列条目，并且通过维护多个累加器（例如，需要总时间和队列迭代次数）来计算您所需的时间任务完成而不需要操作队列的数组结构，甚至不需要数组中的入口值。

更精细的细节还需要进行处理，但是进行这种分析所需的时间应取决于最初的队列中，而不是剩余每项任务的时间的长度。

程序javascript的时间复杂度，用于计划任务

相关推荐