Я ищу временные и пространственные сложности вышеуказанных алгоритмов, но я не могу найти их в Google, я потратил более двух дней без какого-либо результата. Я был бы очень благодарен, если бы вы, ребята, мне помогли.
Временные и пространственные сложности алгоритмов сжатия, таких как LZ4, Snappy, Zstandard и Deflate
comment
en.wikipedia.org/wiki/. Последние несколько абзацев этого раздела могут оказаться полезными.
- person user3386109   schedule 25.10.2018
comment
Добро пожаловать в StackOverflow. Пожалуйста, прочтите и следуйте инструкциям по размещению сообщений в справочной документации, предложенным при создании этой учетной записи. По теме, как задать и ... идеальный вопрос применяется здесь. StackOverflow не является ресурсом для проектирования, кодирования, исследований или учебных пособий.
- person Prune   schedule 25.10.2018
Ответы (1)
Все они равны O(1) по пространству и O(n) по времени, где n — размер входных данных. Они предназначены для потокового сжатия и распаковки, когда количество данных, которые можно пропустить, бесконечно, и нет ни роста памяти, ни сверхлинейного роста времени из-за обработки большего количества данных.
(Deflate — это формат, а не алгоритм, поэтому мой ответ касается широко используемой реализации сжатия в формате deflate, то есть zlib.)
person
Mark Adler
schedule
25.10.2018