python - zlib 的 deflate 算法的时间复杂度

Question

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

我知道在 Python 中这个算法是通过 zlib.compress 函数提供的。

推测相应的解压算法具有相同或更好的复杂度。

Answer 1

时间复杂度是指处理时间随输入大小变化的方式。对于 zlib 和我所知道的任何其他压缩方案，压缩和解压缩都是 O(n)。时间与输入的大小成线性关系。

如果您认为解压缩的时间复杂度较低，那么您可能正在考虑 n 前面的常量，而不是 n .是的，解压缩通常比压缩更快，因为那个常数更小。不是因为时间复杂度不同，因为事实并非如此。