给定算法的时间和 Space 复杂度

Question

我有一个算法，想找到它的时间和 space 复杂度。算法是

 Algorithm for Scheduling
 INPUT:P1,P2, PN // N processes
 do
  Sort processes in ascending according to their burst time 
  TQ = median of burst time of processes 
  For (i=1 to N )
   Assign TQ to Process Pi 
   If Burst time of process i < TQ 
    remove Process i from array
   Else
    BT of process i = BT of process i - TQ
  Compute waiting time for all process in array
 While (array of processes != empty)

如何计算这个算法的时间和space复杂度？

Answer 1

在评论中，您声明需要 O(1) 来更新进程的等待时间，因此这意味着以下行需要 O(N ):

Compute waiting time for all process in array

关于remove操作你也建议是O(1)，虽然你不应该将相应的等待时间设置为零，因为那样会影响数组上的其他操作（如排序和获取中位数）。更好的方法是将最后一个进程复制到槽 i，然后从数组中删除最后一个元素。那将是 O(1).

for 循环的执行需要 O(N)。在排序后的数组中求中位数也是O(N)，所以在do体中时间复杂度最大的操作就是排序：O (N⋅logN)

在 do 循环的每次迭代中，数组大小 (N) 减半。

所以我们有以下等式（省略大 O 符号）：

T(N) = N⋅log(N) + T(N/2)
     = N⋅log(N) + (N/2)⋅log(N/2) + (N/4)⋅log(N/4) + ...
     = N⋅(log(N) + (1/2)⋅log(N/2) + (1/4)⋅log(N/4) + ...)

现在 log(N/c) = log(N) - log(c)，所以我们可以对术语进行分组如下：

     = N⋅((1 + 1/2 + 1/4 + ...)⋅log(N) - log(2)/2 - log(4)/4 - log(8)/8 - ...)
     = N⋅(2⋅log(N) - log(2)/2 - log(4)/4 - log(8)/8 - ...)
     < 2N⋅log(N)

所以我们开始时 T(N) 至少是 O(N⋅log(N))，我们推导出它最多是 O(N⋅log(N))，所以我们对时间复杂度有严格的限制：

O(N⋅log(N))

给定算法的时间和 Space 复杂度

Time and Space Complexity of given algorithm

algorithm

complexity-theory

time-complexity

space-complexity