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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

Графики

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

См. также

Ссылки

^ Д. Эппштейн , З. Галил и Г. Ф. Итальяно . «Алгоритмы динамических графов». В Справочнике CRC по алгоритмам и теории вычислений , глава 22. CRC Press, 1997.

Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее .

[1] Д. Эппштейн , З. Галил и Г. Ф. Итальяно . «Алгоритмы динамических графов». В Справочнике CRC по алгоритмам и теории вычислений , глава 22. CRC Press, 1997.

[1]