假设我们从一个文本文件开始，例如：
a 00
b 01
c 10
d 11
00000001011011
该算法将是典型的算法，您使用前缀构建霍夫曼树，在遍历树时读取编码位，直到到达叶子，然后在该叶子处返回字符。
有人可以解释我如何确定运行时间和空间复杂度吗？
问问题
24843 次
2 回答
9
基本上在霍夫曼树上存在三种方法，构造、编码和解码。时间复杂度可能会有所不同。
我们应该首先注意到（参见 Wikipedia [link]）：
很多情况下，这里的算法选择时间复杂度并不是很重要，因为这里的 n 是字母表中的符号个数，通常是一个很小的数字（与要编码的消息长度相比）；而复杂性分析则关注当 n 变得非常大时的行为。
- 如果对输入概率进行排序，则构造的复杂性是线性的 (O(n))，请参阅本文。在大多数情况下，我们使用贪婪的 O(n*log(n)) 构造方法： http ://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html
- 如果您为所有符号构建双向哈希表，则编码和解码都将是恒定的 (O(1))。
于 2013-12-02T04:47:31.737 回答
4
假设一个长度为 n 的编码文本字符串和一个由 k 个符号组成的字母表。
对于每个编码符号，您必须遍历树才能解码该符号。这棵树包含 k 个节点，平均而言，解码一个符号需要 O(log k) 个节点访问。所以时间复杂度是O(n log k)。
树的空间复杂度为 O(k)，解码文本的空间复杂度为 O(n)。
于 2013-12-02T15:30:32.883 回答