我有一个算法，想找到它的时间和空间复杂性。 算法是
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)
如何计算该算法的时空复杂度？
在注释中，您声明需要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((