Algoritmos y Estructuras de Datos (VJ1215)

El algoritmo de Huffman consta de dos etapas:

1. Inicialmente inserta n datos en una cola de prioridad.

2. A continuación hace n iteraciones, en cada una de las cuales realiza dos operaciones de eliminación del mínimo y una operación de inserción.

Con un vector no ordenado, el coste de la etapa 1 sería O(n) realizando n operaciones de inserción, cada una de las cuales cuesta O(1). El coste de la etapa 2 sería O(n²), porque el coste de la inserción sería O(1) pero el coste de la eliminación del mínimo sería O(n). Por tanto, el coste temporal del algoritmo sería O(n + n²) = O(n²).

Con un vector ordenado, el coste de la etapa 1 depende de si se utilizan n operaciones de inserción, en cuyo caso la etapa 1 costaría O(n²), o se emplea un algoritmo de ordenación eficiente en tiempo O(n log n). El coste de la etapa 2 sería O(n²), porque el coste de la inserción sería O(n) aunque el coste de la eliminación del mínimo sería O(1). En cualquier caso, el coste temporal del algoritmo sería O(n²).

Con un árbol binario de búsqueda, el coste de la etapa 1 sería O(n²) realizando n operaciones de inserción. El coste de la etapa 2 también sería O(n²), porque tanto la inserción como la eliminación del mínimo cuestan O(n). Por tanto, el coste temporal del algoritmo sería O(n²).

Con un árbol AVL, el coste de la etapa 1 sería O(n log n) realizando n operaciones de inserción. El coste de la etapa 2 también sería O(n log n), porque tanto la inserción como la eliminación del mínimo cuestan O(log n). Por tanto, el coste temporal del algoritmo sería O(n log n).

Con un montículo binario, el coste de la etapa 1 depende de si se utilizan n operaciones de inserción, en cuyo caso la etapa 1 costaría O(n log n), o se emplea el algoritmo de construcción de montículos en tiempo O(n). El coste de la etapa 2 sería O(n log n), porque tanto la inserción como la eliminación del mínimo cuestan O(log n). En cualquier caso, el coste temporal del algoritmo sería O(n log n).