Большая сложность алгоритмов - LZW и Хаффман

Question

Каковы пространственные и временные сложности в обозначениях Big O для алгоритмов сжатия Лемпеля-Зива-Уэлча и Хаффмана?Google подводит меня.

Спасибо,

Франциско

Answer 1

Поскольку размер словаря является фиксированным и не зависит от длины ввода, LZW находится в O ( n ), поскольку каждый байт читается только один раз, а сложность операции для каждого символ постоянный.

И Кодировка Хаффмана также находится в O ( n ): сначала вы подсчитываете количество вхождений для каждого входного байта, затем сортируете его и строите выходную кодировку.

Answer 2

Зависит от реализации.Они все время поправляются.«Хаффман» - слишком распространенный термин.Например, вы могли бы иметь в виду явное дерево, неявное, динамическое ... Но в любом случае, я думаю, что если вы сделаете это очень умным, вы сможете реализовать почти любой "Хаффман" на O (n) , с длиной текста n .

LZW также зависит от реализации.Я не знаю, какие обычные реализации имеют «О».Я думаю, с большими таблицами у вас, вероятно, есть что-то вроде O (n log n) , но это всего лишь предположение.