Пространственно-временной компромисс

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

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

Первый метод из группы состоит в предварительной полной или частичной обработке входных данных с сохранением полученной дополнительной информации для ускорения решения задачи.

Другой метод из этой группы просто использует дополнительную память для того, чтобы обеспечить более быстрый и/или более гибкий доступ к данным.

Ещё один метод разработки алгоритмов, относящийся к пространственно-временному компромиссу, – это динамическое программирование, которое является разновидностью метода уменьшения размера задачи, но вместо того чтобы решать перекрывающиеся (совпадающие) подзадачи снова и снова, динамическое программирование предлагает решить каждую из меньших подзадач только один раз, записывая её решение в таблице.

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

Временная эффективность двух основных алгоритмов обхода — поиск в ширину и поиск в глубину — зависит от структуры данных, используемой для представления графов: она равна `Theta(n^2)` для представления с помощью матрицы смежности, `Theta(n + m)` для представления с применением списков смежных вершин.

Задания для практики

1. Что общего имеет динамическое программирование с методом декомпозиции? В чем главное отличие между этими двумя методами?