Curso 2023/2024
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.