Динамическая задача (алгоритмы)

Динамические проблемы в теории вычислительной сложности — это проблемы, сформулированные в терминах изменения входных данных. В наиболее общем виде проблема этой категории обычно формулируется следующим образом:

Для заданного класса входных объектов найдите эффективные алгоритмы и структуры данных для ответа на определенный запрос о наборе входных объектов каждый раз, когда входные данные изменяются, т. е. объекты вставляются или удаляются.

Задачи этого класса имеют следующие показатели сложности:

Пространство – объем памяти, необходимый для хранения структуры данных;
Время инициализации – время, необходимое для первоначального построения структуры данных;
Время вставки – время, необходимое для обновления структуры данных при добавлении еще одного входного элемента;
Время удаления – время, необходимое для обновления структуры данных при удалении входного элемента;
Время запроса – время, необходимое для ответа на запрос;
Другие операции, специфичные для рассматриваемой проблемы

Общий набор вычислений для динамической задачи называется динамическим алгоритмом .

Многие алгоритмические задачи, сформулированные в терминах фиксированных входных данных (в данном контексте называемые статическими задачами и решаемые статическими алгоритмами ), имеют содержательные динамические версии.

Особые случаи

Инкрементные алгоритмы , или онлайн-алгоритмы , — это алгоритмы, в которых допускается только добавление элементов, возможно, начиная с пустых/тривиальных входных данных.

Декрементные алгоритмы — это алгоритмы, в которых допускается только удаление элементов, начиная с инициализации полной структуры данных.

Если разрешены как добавления, так и удаления, алгоритм иногда называют полностью динамическим .

Примеры

Максимальный элемент

Статическая проблема: Для набора из N чисел найдите максимальное.

Задача может быть решена за O(N) времени.

Динамическая проблема: Для начального набора из N чисел динамически поддерживайте максимальное число, когда разрешены вставки и удаления.

Хорошо известным решением этой проблемы является использование самобалансирующегося бинарного дерева поиска . Оно занимает место O(N), может быть изначально построено за время O(N log N) и обеспечивает время вставки, удаления и запроса в O(log N).

Проблема обслуживания приоритетной очереди: Это упрощенная версия этой динамической проблемы, где требуется удалить только максимальный элемент. Эта версия может обойтись более простыми структурами данных.

Графики

Для заданного графа сохранить его параметры, такие как связность, максимальная степень, кратчайшие пути и т. д., когда разрешены вставка и удаление его ребер. ^[1]

Смотрите также

Ссылки

^ D. Eppstein , Z. Galil и GF Italiano . "Алгоритмы на динамических графах". В CRC Handbook of Algorithms and Theory of Computation , Глава 22. CRC Press, 1997.