压缩算法(如LZ4、Snappy、Zstandard和Deflate )的时空复杂性

Question

我正在寻找上述算法的时间和空间复杂性，但我无法在谷歌上找到它，我浪费了两天多没有任何结果，如果你们能帮我的话，我将非常感激。

Answer 1

它们在空间上都是O(1)，在时间上都是O(n)，其中n是输入的大小。它们是为流压缩和解压缩设计的，在这种情况下，可以运行的数据量是无限的，并且由于处理更多的数据，内存没有增长，时间上也没有超线性增长。

(平减是一种格式，而不是一种算法，所以我的答案是关于压缩到平减格式的常用实现，即zlib)。