Estructuras de datos | Cola | Pregunta 10

Considere la siguiente operación junto con las operaciones Enqueue y Dequeue en
colas, donde k es un parámetro global.

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

¿Cuál es la complejidad temporal en el peor de los casos de una secuencia de n operaciones MultiDequeue() en una cola inicialmente vacía? (GATE CS 2013)
(A) $\Theta(n)$
(B) $\Theta(n + k)$
(C) $\Theta(nk)$
(D) $\Theta(n^2)$

(A) A
(B) B
(C) C
(D) D

Respuesta: (A)
Explicación: dado que la cola está vacía inicialmente, la condición del bucle while nunca se cumple. Entonces la complejidad del tiempo es $\Theta(n)$ .
Cuestionario de esta pregunta

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta