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. Considere las siguientes afirmaciones con respecto al algoritmo de codificación de Huffman.
S1: 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.
S2: si la array de entrada está ordenada, existe un algoritmo de tiempo lineal.
S3: 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.
¿Cuál de las siguientes opciones es la correcta?
(A) La declaración S1 es correcta, las declaraciones S2 y S3 no son correctas.
(B) Las declaraciones S1 y S2 son correctas y la declaración S3 no es correcta.
(C) Las declaraciones S2 y S3 son correctas y la declaración S1 no es correcta.
(D) Todas las afirmaciones S1, S2 y S3 son correctas.
Respuesta: (D)
Explicación: Todas las afirmaciones dadas son correctas.
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