Algoritmos y Estructuras de Datos (VJ1215)
Curso 2023/2024
Algoritmos y Estructuras de Datos (VJ1215)
Curso 2023/2024
| insertar | eliminarMínimo | consultarMínimo | |
|---|---|---|---|
| (i) vector no ordenado | O(1) | O(n) | O(1) |
| (ii) vector ordenado | O(n) | O(1) | O(1) |
| (iii) lista enlazada no ordenada | O(1) | O(n) | O(1) |
| (iv) lista enlazada ordenada | O(n) | O(1) | O(1) |
En las implementaciones (i) y (iii) mantendríamos un atributo adicional que tenga el valor mínimo, para que la operación consultarMínimo tenga coste O(1). Podemos hacer que ese atributo guarde la posición del valor mínimo, para que en la operación eliminarMínimo no haya que buscarlo. Pagaremos un coste O(n) para encontrar el nuevo mínimo tras la eliminación. Mantenerlo actualizado al insertar un nuevo dato cuesta O(1).
En la implementación (ii) emplearíamos un vector circular o un vector que crece por el lado donde se encuentra el mínimo, para que la operación eliminarMínimo tenga coste O(1).