Was sind die Raum- und Zeitkomplexitäten in der Big-O-Notation für die Lempel-Ziv-Welch- und Huffman-Kompressionsalgorithmen? Google versagt mich.
Danke,
Francisco
Da die Wörterbuchgröße fest und unabhängig von der Eingabedauer ist, LZW ist in O ( n ), da jedes Byte nur einmal gelesen wird und die Komplexität der Operation für jedes Zeichen konstant ist.
Und Huffman-Codierung ist auch in O ( n ): Zuerst zählt man die Zahl von Vorkommen für jedes Eingangsbyte, dann sortieren Sie es und bauen die Ausgangskodierung auf.
Hängt von der Implementierung ab. Sie werden die ganze Zeit besser. "Huffman" ist ein etwas zu gewöhnlicher Begriff. Zum Beispiel könnte man einen expliziten Baum meinen, einen impliziten, einen dynamischen ... Aber auf jeden Fall, wenn du es schlau machst, solltest du in der Lage sein, fast jedes "Huffman" auf O (n) zu implementieren, mit n ist die Textlänge.
LZW ist auch implementierungsabhängig. Ich weiß nicht, was "O" gängige Implementierungen haben. Ich denke, mit großen Tabellen haben Sie wahrscheinlich etwas wie O (n log n) , aber das ist nur eine Vermutung.
Tags und Links algorithm time-complexity compression big-o space-complexity