LZ4、Snappy、Zstandard 和 Deflate 等压缩算法的时间和空间复杂度

Question

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

Answer 1

它们在空间上都是 O(1)，在时间上都是O( n )，其中n是输入的大小。它们专为流压缩和解压而设计，其中可以运行的数据量是无限的，并且不会因为处理更多数据而导致内存增长或时间上的超线性增长。

（Deflate 是一种格式，而不是一种算法，所以我的回答是关于压缩到 deflate 格式的常用实现，即 zlib。）