算法的大O复杂性 - LZW和Huffman

Question

对于Lempel-Ziv-Welch和Huffman压缩算法,Big O表示法的空间和时间复杂性有哪些？谷歌让我失望.

谢谢,

弗朗西斯科

Answer 1

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

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

Answer 2

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

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