La codificación Huffman es un algoritmo de compresión de datos sin pérdidas. El carácter más frecuente obtiene el código más pequeño y el carácter menos frecuente obtiene el código más grande.
¿Cuál de las siguientes opciones es falsa con respecto al algoritmo de codificación de Huffman?
(A) La complejidad temporal del algoritmo de Huffman es O(nlogn). Usando un montón para almacenar el peso de cada árbol, cada iteración requiere tiempo O (logn) para determinar el peso más barato e insertar el nuevo peso. Hay O(n) iteraciones, una para cada elemento.
(B) Si la array de entrada está ordenada, existe un algoritmo de tiempo lineal.
(C) Un enfoque de divide y vencerás podría hacernos preguntar qué personajes deberían aparecer en los subárboles izquierdo y derecho e intentar construir el árbol de arriba hacia abajo. Al igual que con el árbol de búsqueda binario óptimo, esto conducirá a un algoritmo de tiempo exponencial.
(D) Ninguno de estos.
Respuesta: (D)
Explicación:Todas las declaraciones dadas son correctas con respecto al algoritmo de codificación de Huffman .
La opción (D) es verdadera.
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