c - 查找代码的复杂性

Question

考虑以下操作以及队列上的入队和出队操作，其中 k 是全局参数

MultiDequeue ( Q )
{
  m=k
  while ( Q is not empty ) and (m > 0 ) 
  {
    Dequeue ( Q )
    m = m −1
  }
}

在最初为空的队列上，一系列 n 个队列操作的最坏情况时间复杂度是多少？(A) Θ (n) (B) Θ (n + k ) (C) Θ (nk )

这不是我的作业，它在我的考试中被问到……n 根据我的说法，它应该是 (n + k)。

它不能是 (n)，因为在 while 循环中有一个 and 条件，所以它同时依赖于 n 和 k....并且由于它不是嵌套循环或某个矩阵，所以它不是 (nk)....

我以这种方式解决了它，如果 while ( Q is not empty ) 而不是 while ( Q is not empty ) and (m > 0 ) 那么时间复杂度将是 (n) 如果 m = 4 它应该是 n+k而不是 nk .....这实际上是一个猜测

score 2 · Accepted Answer

无论 n Enqueue、Dequeue 还是 MultiDequeue 的顺序是原始 O(1) 操作的数量，Enqueue/Dequeue 都不能超过 2*n。所以它是O（n）。

score 1 · Accepted Answer

队列最初是空的，所以while循环的条件永远不会为真，所以时间复杂度将是Theta(n)。或者其他方式，如果只执行入队和出队操作，那么它也将是 Theta(n)（n 次插入和 n 次删除）。

score -3 · Accepted Answer

-3

答案是 C。在最坏的情况下，您将执行 n 次入队操作。

于 2013-10-03T16:36:13.533 回答

3 回答 3