Динамические проблемы в теории сложности вычислений - это проблемы, сформулированные в терминах изменяющихся входных данных. В самом общем виде проблема этой категории обычно формулируется следующим образом:
- Учитывая класс входных объектов, найдите эффективные алгоритмы и структуры данных для ответа на определенный запрос о наборе входных объектов каждый раз, когда входные данные изменяются, т. Е. Объекты вставляются или удаляются.
Задачи этого класса имеют следующие меры сложности:
- Пространство - объем памяти, необходимый для хранения структуры данных;
- Время инициализации - время, необходимое для первоначального построения структуры данных;
- Время вставки - время, необходимое для обновления структуры данных при добавлении еще одного элемента ввода;
- Время удаления - время, необходимое для обновления структуры данных при удалении элемента ввода;
- Время запроса - время, необходимое для ответа на запрос;
- Другие операции, относящиеся к рассматриваемой проблеме
Общий набор вычислений для динамической задачи называется динамическим алгоритмом .
Многие алгоритмические проблемы, сформулированные в терминах фиксированных входных данных ( в данном контексте называемые статическими проблемами и решаемые статическими алгоритмами ), имеют значимые динамические версии.
Особые случаи [ править ]
Инкрементальные алгоритмы или онлайн-алгоритмы - это алгоритмы, в которых разрешено только добавление элементов, возможно, начиная с пустых / тривиальных входных данных.
Алгоритмы декремента - это алгоритмы, в которых разрешено только удаление элементов, начиная с инициализации полной структуры данных.
Если разрешены и добавления, и удаления, алгоритм иногда называют полностью динамическим .
Примеры [ править ]
Максимальный элемент [ править ]
- Статическая проблема
- Для набора из N чисел найдите максимальное.
Проблема может быть решена за время O (N).
- Динамическая проблема
- Для начального набора из N номеров динамически поддерживать максимальное значение, когда разрешены вставка и удаление.
Хорошо известным решением этой проблемы является использование самобалансирующегося двоичного дерева поиска . Он занимает пространство O (N), может быть изначально построен за время O (N log N) и обеспечивает время вставки, удаления и запроса в O (log N).
- Проблема обслуживания приоритетной очереди
- Это упрощенная версия этой динамической задачи, в которой требуется удалить только максимальный элемент. Эта версия может работать с более простыми структурами данных.
Графики [ править ]
Для данного графа сохраните его параметры, такие как связность, максимальная степень, кратчайшие пути и т. Д., Когда разрешены вставка и удаление его ребер. [1]
См. Также [ править ]
Ссылки [ править ]
- ^ D. Eppstein , Z. Galil и GF Italiano . «Алгоритмы динамического графа». В Справочнике по алгоритмам и теории вычислений CRC, глава 22. CRC Press, 1997.
