霍夫曼解码算法的运行时间和空间复杂度是多少？

Question

假设我们开始使用如下文本文件:

a 00 
b 01
c 10
d 11

00000001011011

该算法将是您使用前缀来构建霍夫曼树的典型算法,在遍历树时读取编码位,直到到达叶子,然后在该叶子处返回字符.

有人可以解释我如何确定运行时间和空间复杂度？

Answer 1

基本上,霍夫曼树上有三种方法,构造,编码和解码.时间复杂度可能彼此不同.

我们应该首先注意到(见维基百科[link]):

在许多情况下,时间复杂度在这里选择算法时并不是非常重要,因为这里的n是字母表中符号的数量,通常是一个非常小的数字(与要编码的消息的长度相比); 而复杂性分析涉及当n增长到非常大时的行为.

1. 如果对输入概率进行排序,则构造的复杂性是线性的(O(n)),参见本文.在大多数情况下,我们使用贪婪的O(n*log(n))构造方法:http: //www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html
2. 如果为所有符号构建双向哈希表,则编码和解码都将是常量(O(1)).