Algoritmos y Estructuras de Datos (VJ1215)
Curso 2022/2023
Algoritmos y Estructuras de Datos (VJ1215)
Curso 2022/2023
En el caso del TAD Multiconjunto tendríamos estos costes temporales:
| insertar | eliminar | buscar | |
|---|---|---|---|
| (i) vector no ordenado | O(1) | O(n) | O(n) |
| (ii) vector ordenado | O(n) | O(n) | O(log n) |
| (iii) lista enlazada no ordenada | O(1) | O(n) | O(n) |
| (iv) lista enlazada ordenada | O(n) | O(n) | O(n) |
Suponemos que la talla máxima del vector es conocida a priori y no se redimensiona, tal como indica el enunciado.
En el caso del TAD Conjunto, las operaciones de inserción pasarían a costar siempre O(n) para comprobar que el elemento a insertar no está duplicado.