algorithm - 算法的大 O 复杂度 - LZW 和 Huffman

Question

在大 O 表示法中，Lempel-Ziv-Welch 和 Huffman 压缩算法的空间和时间复杂度是多少？谷歌让我失望了。

谢谢，

弗朗西斯科

Answer 1

由于字典大小是固定的并且与输入长度无关，因此LZW在 O( n ) 中，因为每个字节只读取一次，并且每个字符的操作复杂度是恒定的。

霍夫曼编码也在 O( n ) 中：首先计算每个输入字节的出现次数，然后对其进行排序并构建输出编码。

Answer 2

取决于实施。他们一直在变得更好。“霍夫曼”这个词有点太常见了。例如，您可能指的是显式树、隐式树、动态树……但无论如何，我想如果您做得非常聪明，您应该能够在O(n)上实现几乎任何“霍夫曼” ，与n是文本长度。

LZW 也依赖于实现。我不知道“O”常见实现有什么。我猜对于大表，你可能有类似O(n log n)的东西，但这只是一个猜测。