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 不为空 ) 存在而不是 while ( Q 不为空 ) 和 (m > 0 )，那么时间复杂度将为 (n)，如果 m = 4 则时间复杂度应该为 (n) n+k 而不是 nk...这实际上是一个猜测

Answer 1

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