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

Не путать с Динамическое программирование.

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

Графики

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

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

Рекомендации

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