¿Cuál es la complejidad de tiempo en el peor de los casos de insertar n elementos en una lista enlazada vacía, si la lista enlazada necesita mantenerse ordenada?
(A) Θ(n)
(B) Θ(n log n)
(C) Θ(n 2 )
(D) Θ(1)
Respuesta: (C)
Explicación: Esta pregunta es ambigua: “necesita mantenerse ordenada orden”, hay dos casos posibles:
- Debe mantenerse ordenado en cada paso (después de cada inserción) .
Cuando estamos insertando un elemento en una lista enlazada vacía y para realizar una lista ordenada de cada elemento, tomará O (n 2 ).
Cada inserción en una lista enlazada ordenada tomará θ(n) y, por lo tanto, el costo total para n operaciones es θ(n 2 ). - Debe mantenerse ordenado en el paso final (solo después de todas las inserciones) .
Cuando estamos insertando todos los elementos en una lista enlazada vacía y para realizar una lista ordenada ( usando la ordenación por fusión ) después de insertar todos los elementos tomará tiempo O (n log n).
La respuesta oficial de GATE es Θ(n 2 ).
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