Компромисс пространство-время или компромисс время-память в информатике — это случай, когда алгоритм или программа обменивает увеличение использования пространства на уменьшение времени. Здесь пространство относится к хранилищу данных, потребляемому при выполнении данной задачи ( ОЗУ , жесткий диск и т. д.), а время относится к времени, затраченному на выполнение данной задачи ( время вычисления или время отклика ).
Полезность данного компромисса между пространством и временем зависит от соответствующих фиксированных и переменных затрат (например, скорости процессора , места для хранения) и подвержена убывающей отдаче .
Биологическое использование компромиссов времени и памяти можно увидеть на более ранних стадиях поведения животных . Использование накопленных знаний или кодирование реакций на стимулы как «инстинкты» в ДНК позволяет избежать необходимости «расчетов» в критических по времени ситуациях. Более конкретно для компьютеров таблицы поиска были реализованы с самых первых операционных систем. [ нужна ссылка ]
Распространенной ситуацией является алгоритм, включающий таблицу поиска : реализация может включать всю таблицу, что сокращает время вычислений, но увеличивает объем необходимой памяти, или может вычислять записи таблицы по мере необходимости, увеличивая время вычислений, но уменьшая требования к памяти.
Компромисс пространства и времени можно применить к проблеме хранения данных. Если данные хранятся в несжатом виде, они занимают больше места, но доступ к ним занимает меньше времени, чем если бы данные хранились в сжатом виде (поскольку сжатие данных уменьшает объем занимаемого места, но для запуска алгоритма распаковки требуется время ). В зависимости от конкретного экземпляра проблемы применим любой из этих способов. Также бывают редкие случаи, когда можно напрямую работать со сжатыми данными, например, в случае со сжатыми растровыми индексами , где быстрее работать со сжатием, чем без сжатия.
Сохранение только SVG - источника векторного изображения и его рендеринг в виде растрового изображения каждый раз, когда запрашивается страница, означало бы обмен времени на пространство; используется больше времени, но меньше места. Рендеринг изображения при изменении страницы и сохранение визуализированных изображений означало бы обмен места на время; используется больше места, но меньше времени. Этот метод более известен как кэширование .