Lempel-Ziv-Welch および Huffman 圧縮アルゴリズムの Big O 表記での空間と時間の複雑さは何ですか? グーグルは私を失望させています。
ありがとう、
フランシスコ
9942 次
2 に答える
9
辞書のサイズは固定されており、入力の長さとは無関係であるため、LZWは O( n ) になります。これは、各バイトが 1 回だけ読み取られ、各文字の操作の複雑さが一定であるためです。
また、ハフマン エンコーディングも O( n ) にあります。まず、各入力バイトの出現回数をカウントし、それを並べ替えて、出力エンコーディングを構築します。
于 2011-05-31T15:29:43.270 に答える
4
実装に依存します。彼らは常に良くなっています。「ハフマン」は少し一般的な用語です。たとえば、明示的なツリー、暗黙的なツリー、動的なツリーを意味する可能性があります...しかし、いずれにせよ、非常に巧妙に行うと、 O(n)でほぼすべての「ハフマン」を実装できるはずです。nはテキスト長です。
LZW も実装依存です。「O」の一般的な実装に何が含まれているかはわかりません。大きなテーブルでは、おそらくO(n log n)のようなものがあると思いますが、それは単なる推測です。
于 2011-05-31T15:22:56.187 に答える