假设我们有一个文本文件：
a 00
b 01
c 10
d 11
00000001011011
算法通常是使用前缀构建哈夫曼树，读取编码位并遍历树，直到到达叶子节点，然后返回该叶子节点中的字符。
请问有人能解释一下如何确定运行时间和空间复杂度吗？
一个Huffman解码算法的运行时间和空间复杂度是什么？
4
- atkayla
2
维基页面上说了什么？ - Mitch Wheat
你已经描述了一个实现这个功能的算法，但是你也有代码吗？时间复杂度可能会根据你的实现方式而有所不同。 - Philip Liberato
2个回答
9
基本上，哈夫曼树有三种方法：构建、编码和解码。它们的时间复杂度可能各不相同。
首先需要注意的是（参见Wikipedia [link]）：
“在许多情况下，时间复杂度并不是算法选择中非常重要的因素，因为n是字母表中符号的数量，通常是一个非常小的数字（与要编码的消息长度相比）；而复杂性分析关注的是当n变得非常大时的行为。”
以下是两种方法的复杂度：
1.如果输入概率已排序，则构造的复杂度为线性（O(n))，请参阅此paper。在大多数情况下，我们使用贪心O(n*log(n))构造方法： http://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html 2.如果为所有符号构建双向哈希表，则编码和解码均为常量（O(1))。
首先需要注意的是（参见Wikipedia [link]）：
“在许多情况下，时间复杂度并不是算法选择中非常重要的因素，因为n是字母表中符号的数量，通常是一个非常小的数字（与要编码的消息长度相比）；而复杂性分析关注的是当n变得非常大时的行为。”
以下是两种方法的复杂度：
1.如果输入概率已排序，则构造的复杂度为线性（O(n))，请参阅此paper。在大多数情况下，我们使用贪心O(n*log(n))构造方法： http://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html 2.如果为所有符号构建双向哈希表，则编码和解码均为常量（O(1))。
- Tao HE
4
假设有一个长度为n的编码文本字符串和一个由k个符号组成的字母表。
对于每个编码符号，您需要遍历树来解码该符号。树包含k个节点，并且平均而言，解码一个符号需要O(log k)个节点访问。因此，时间复杂度为O(n log k)。
树的空间复杂度为O(k)，解码后文本的空间复杂度为O(n)。
对于每个编码符号，您需要遍历树来解码该符号。树包含k个节点，并且平均而言，解码一个符号需要O(log k)个节点访问。因此，时间复杂度为O(n log k)。
树的空间复杂度为O(k)，解码后文本的空间复杂度为O(n)。
- Jim Mischel
3
为什么时间复杂度是O(k)呢？在最坏情况下，输出树可能是一个完全二叉树，具有k+k\2+k\4+...+1=O(k^2)个节点。 - so.very.tired
@so.very.tired：请重新阅读我的回答。我说的是空间复杂度为O(k)。有k个字符，就有k个节点在树中。 - Jim Mischel
抱歉我一直想问：“为什么空间复杂度是……等等……”，我写错了，应该是“空间”而不是“时间”。
在哈夫曼树中，字母由终端节点表示（不仅仅是任何节点），因此对于k个字符，有k个终端节点，这意味着树最终可能会有O(k^2)个节点（终端和内部节点）。 - so.very.tired
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接