PUERTA | GATE-CS-2015 (Conjunto 1) | Pregunta 50

Un algoritmo realiza (logN) ^1/2 operaciones de búsqueda, N operaciones de inserción, (logN) ^1/2 operaciones de eliminación y (logN) ^1/2 operaciones de disminución de clave en un conjunto de elementos de datos con claves extraídas de un conjunto ordenado linealmente . Para una operación de eliminación, se proporciona un puntero al registro que debe eliminarse. Para la operación de disminución de clave, se proporciona un puntero al registro que tiene su clave disminuida. ¿Cuál de las siguientes estructuras de datos es la más adecuada para el uso del algoritmo, si el objetivo es lograr la mejor complejidad asintótica total considerando todas las operaciones?
(A) Array no ordenada
(B) Min-heap
(C) Array ordenada
(D) Lista ordenada doblemente enlazada

Respuesta: (A)
Explicación: la complejidad de tiempo de la inserción en una array no ordenada es O(1), O(Logn) en Min-Heap, O(n) en una array ordenada y una DLL ordenada.

1. Para una array no ordenada, siempre podemos insertar un elemento al final e insertarlo en el tiempo O (1)
2. Para Min Heap, la inserción toma tiempo O (Log n). Consulte Operaciones de almacenamiento dinámico binario para obtener más información.
3. Para una array ordenada, la inserción toma O (n) tiempo, ya que es posible que tengamos que mover todos los elementos en el peor de los casos.
4. Para una lista ordenada doblemente enlazada, la inserción toma O (n) tiempo para encontrar la posición del elemento que se insertará.

Dado que el número de operaciones de inserción es asintóticamente mayor, se prefiere la array no ordenada.
Cuestionario de esta pregunta