zlib的deflate算法时间复杂度

Question

3

Zlib的deflate算法的时间复杂度是多少？

我知道在Python中，可以通过zlib.compress函数使用这个算法。

大概相应的解压缩算法具有相同或更好的复杂度。

- ehremo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Adler · Accepted Answer

时间复杂度指的是处理时间随输入大小的增长而扩展的程度。对于zlib和我所知的其他压缩方案，无论是压缩还是解压缩都是O（n）。处理时间随着输入大小呈线性增长。

如果你认为解压缩的时间复杂度在某种程度上要少些，那么也许你考虑的是N前面的常数，而不是N本身。是的，解压缩通常比压缩快，因为该常数较小，而不是因为时间复杂度不同。