c - コードの複雑さを見つける

Question

キューでの Enqueue および Dequeue 操作とともに、次の操作を検討してください。ここで、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）であるべきです.

while ループに and 条件があり、n と k の両方に依存しているため、(n) にはなりません。また、ネストされたループまたは行列ではないため、(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

答えは C です。最悪の場合、n 回のエンキュー操作を実行することになります。

3 に答える 3