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

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

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

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

如果对输入概率进行排序,则构造的复杂性是线性的(O(n)),参见本文.在大多数情况下,我们使用贪婪的O(n*log(n))构造方法:http: //www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html

如果为所有符号构建双向哈希表,则编码和解码都将是常量(O(1)).