Codeword constructed by Huffman's algorithm has average length of at most log n
-
06-11-2019 - |
Pergunta
I am interested in the following question:
Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $\log n$, where $n$ is the number of codewords.
I'm thinking of a worst case when the full binary tree (generated by Huffman's algorithm) has height $n-2$, but I still have to take the letter frequency into account, and I am stuck.
(Also I observed that the letter frequency shrinks by a factor of two when traversing down the tree.)
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange