zlibの収縮アルゴリズムの時間複雑度

Question

Zlibの収縮アルゴリズムの複雑さはどのくらいですか？

私は、Pythonではこのアルゴリズムがzlib.compress関数で利用できることを理解しています。おそらく対応する解凍アルゴリズムは同じかより良い複雑さを有すると思われる。

Answer 1

時間の複雑さは、処理時間が入力のサイズに応じてどのように変化するかです。 zlibと私が知っている他の圧縮方式では、圧縮と圧縮解除の両方でO（n）です。時間は入力のサイズに比例して変化します。

あなたはn個とは対照的に、解凍の時間複雑性は、何らかの形で、おそらくあなたはn個の前に定数を考えている以下であることを考えている場合。はい、圧縮率は圧縮率よりも速いため、通常は圧縮率よりも速いです。時間の複雑さが異なるからではなく、そうでないからです。