質問

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.)

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top