Компромисс между пространством и временем

Компромисс пространства-времени , также известный как компромисс времени-памяти или алгоритмический пространственно-временной континуум в информатике, представляет собой случай, когда алгоритм или программа обменивает увеличение использования пространства на уменьшение времени. Здесь пространство относится к хранилищу данных , потребляемому при выполнении данной задачи ( ОЗУ , жесткий диск и т. д.), а время относится к времени, затрачиваемому на выполнение данной задачи ( время вычисления или время ответа ).

На полезность данного компромисса между пространством и временем влияют соответствующие постоянные и переменные затраты (например, скорость процессора , объем памяти) и подвержена убывающей отдаче .

История

Биологическое использование компромисса между временем и памятью можно увидеть на более ранних стадиях поведения животных . Использование накопленных знаний или кодирование реакций на стимулы как «инстинкты» в ДНК позволяет избежать необходимости «расчетов» в критических по времени ситуациях. Более конкретно для компьютеров, справочные таблицы были реализованы с самых ранних операционных систем. ^{[ нужна ссылка ]}

В 1980 году Мартин Хеллман впервые предложил использовать компромисс между временем и памятью для криптоанализа . ^[1]

Типы компромисса

Таблицы поиска и пересчет

Распространенной ситуацией является алгоритм, включающий таблицу поиска : реализация может включать всю таблицу, что сокращает время вычислений, но увеличивает объем необходимой памяти, или она может вычислять записи таблицы по мере необходимости, увеличивая время вычислений, но уменьшая требования к памяти.

Индексы базы данных и сканирование таблиц

Системы управления базами данных предлагают возможность создавать структуры индексных данных базы данных. Индексы повышают скорость операций поиска за счет дополнительного места. трудоемкие операции полного сканирования таблицы Без индексов для поиска нужных данных иногда требуются .

Сжатые и несжатые данные

К проблеме хранения данных можно применить компромисс между пространством и временем. Если данные хранятся в несжатом виде, они занимают больше места, но доступ занимает меньше времени, чем если бы данные хранились в сжатом виде (поскольку сжатие данных уменьшает объем занимаемого места, но для запуска алгоритма распаковки требуется время ). В зависимости от конкретного случая проблемы, любой из способов является практичным. Также существуют редкие случаи, когда можно напрямую работать со сжатыми данными, например, в случае со сжатыми индексами растровых изображений , где работать со сжатием быстрее, чем без сжатия.

Повторный рендеринг и сохраненные изображения

Хранение только SVG исходного векторного изображения и его отображение в виде растрового изображения каждый раз, когда запрашивается страница, потребует затрат времени на пространство; используется больше времени, но меньше места. Рендеринг изображения при изменении страницы и сохранение визуализированных изображений потребует обмена места на время; используется больше места, но меньше времени. Этот метод более известен как кэширование .

Меньший код по сравнению с развертыванием цикла

Больший размер кода можно обменять на более высокую скорость программы при применении развертывания цикла . Этот метод удлиняет код для каждой итерации цикла, но экономит время вычислений, необходимое для возврата к началу цикла в конце каждой итерации.

Другие примеры

Алгоритмы, которые также используют компромисс между пространством и временем, включают:

Алгоритм «маленького гигантского шага» для вычисления дискретных логарифмов
Радужные таблицы в криптографии, где злоумышленник пытается добиться большего, чем экспоненциальное время, необходимое для атаки методом грубой силы . Таблицы Rainbow используют частично заранее вычисленные значения в хэш-пространстве криптографической хэш-функции для взлома паролей за считанные минуты, а не недели. Уменьшение размера радужной таблицы увеличивает время, необходимое для перебора хеш-пространства.
Атака «встреча посередине» использует компромисс между пространством и временем, чтобы найти криптографический ключ всего за $2^{n+1}$ шифрование (и $O(2^{n})$ пространство) по сравнению с ожидаемым $2^{2n}$ шифрования (но только $O(1)$ пространство) наивной атаки.
Динамическое программирование , при котором временная сложность задачи может быть значительно снижена за счет использования большего объема памяти.
Атака компромисса времени/памяти/данных , которая использует компромисс пространства-времени с дополнительным параметром данных.

См. также

Алгоритмическая эффективность - свойство алгоритма.
Теорема Блюма об ускорении - исключает присвоение произвольным функциям их вычислительной сложности.
Вычислительная сложность - количество ресурсов для выполнения алгоритма.
Вычислительный ресурс — что-то, что необходимо компьютеру для решения проблемы, например этапы обработки или память.
Теорема Савича - Связь между детерминированной и недетерминированной сложностью пространства

Ссылки

^ Хеллман, Мартин (июль 1980 г.). «Криптоаналитический компромисс между временем и памятью». Транзакции IEEE по теории информации . 26 (4): 401–406. CiteSeerX 10.1.1.120.2463 . дои : 10.1109/тит.1980.1056220 . S2CID 552536 .

Внешние ссылки

[1] Хеллман, Мартин (июль 1980 г.). «Криптоаналитический компромисс между временем и памятью». Транзакции IEEE по теории информации . 26 (4): 401–406. CiteSeerX 10.1.1.120.2463 . дои : 10.1109/тит.1980.1056220 . S2CID 552536 .

[1]