Average codeword length in a Huffman tree is $\Omega(\log n)$
-
05-11-2019 - |
質問
Prove that the average codeword length in a Huffman tree is $\Omega(\log n)$, where $n$ is the number of characters.
My try:
I think that the worst case is when the tree is full and all the characters are in the highest level.
Therefore: $n=2^h \to h=\log n$, and the average codeword length is $\Omega(\log n)$.
Am I missing something?
正しい解決策はありません
所属していません cs.stackexchange