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

|| 对于Lempel-Ziv-Welch和Huffman压缩算法，用大O表示法表示的时空复杂度是多少？谷歌让我失望。 谢谢， 弗朗西斯科     
2020-01-23 3 条评论
分享

没有找到相关结果

    已邀请:

    辩谷变充

            由于字典大小是固定的，并且与输入长度无关，因此LZW在O（n）中，因为每个字节仅被读取一次，并且每个字符的操作复杂度是恒定的。 霍夫曼编码也用O（n）表示：首先，对每个输入字节进行计数，然后对其进行排序，并构建输出编码。     
    2020-01-23 0 0
    分享

    联海

            取决于实现。他们一直都在进步。 “霍夫曼”这个术语太常见了。例如，您的意思可能是显式树，隐式树，动态树... 但是无论如何，我想如果您做的非常聪明，您应该能够在O（n）上实现几乎任何\“ Huffman \”，其中n为文本长度。 LZW也依赖于实现。我不知道什么是普通的“ O”实现。我猜对于大表，您可能会有类似O（n log n）的东西，但这仅是一个猜测。     
    2020-01-23 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.059055805206299