¿Cuál es la complejidad temporal de la codificación Huffman?
(A) O(N)
(B) O(NlogN)
(C) O(N(logN)^2)
(D) O(N^2)
Respuesta: (B)
Explicación: O(nlogn) donde n es el número de caracteres únicos. Si hay n Nodes, extractMin() se llama 2*(n – 1) veces. extractMin() toma el tiempo O(logn) ya que llama minHeapify(). Entonces, la complejidad general es O (nlogn).
Ver aquí para más detalles del algoritmo.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA