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
scroll top