Оглавление
Компромисс между пространством и временем
-
Компромисс между пространством и временем
- Обмен увеличением пространства на сокращение времени в алгоритмах и программах.
- Пространство включает объем данных, время – время выполнения задачи.
- Затраты на компромисс могут уменьшаться с ростом скорости процессора и объема памяти.
-
История и биологические примеры
- Животные используют инстинкты для избегания “расчетов” в критических ситуациях.
- В компьютерах справочные таблицы использовались с ранних операционных систем.
- Мартин Хеллман предложил использовать компромисс в криптоанализе в 1980 году.
-
Типы компромиссов
- Таблицы поиска: сокращение времени за счет увеличения памяти или наоборот.
- Индексы баз данных: повышение скорости поиска за счет дополнительного пространства.
- Сжатые данные: экономия места за счет времени на распаковку.
- Кэширование изображений: сохранение изображений для экономии времени рендеринга.
- Меньший размер кода: увеличение скорости за счет удлинения кода.
-
Примеры алгоритмов
- Алгоритмы дискретных логарифмов и радужные таблицы в криптографии используют компромисс.
- Атака “встреча посередине” и динамическое программирование также используют компромисс.
-
Рекомендации и дополнительные ресурсы
- Ссылки на статьи Филиппа Эшслина и другие источники для углубленного изучения темы.