Динамічна задача

Динамічна задача (англ. dynamic problem) в теорії обчислювальної складності належить до задач, які висвітлюються в термінах зміни вхідних даних. У найбільш загальному вигляді проблема в цій категорії зазвичай викладається наступним чином:

Враховуючи клас вхідних об'єктів, знайдіть ефективні алгоритми та структури даних, щоб відповідати на певний запит щодо набору вхідних об'єктів кожного разу, коли змінюються вхідні дані, тобто об'єкти вставляються або видаляються.

Проблеми цього класу мають наступні заходи складності:

Простір — обсяг пам'яті, необхідний для зберігання структури даних;
Час ініціалізації — час, необхідний для початкової побудови структури даних;
Час вставки — час, необхідний для оновлення структури даних, коли додається ще один елемент вводу;
Час видалення — час, необхідний для оновлення структури даних, коли елемент вводу видаляється;
Час запиту — час, необхідний для відповіді на запит;
Інші операції, що стосуються розглянутої проблеми;

Загальний набір розрахунків для динамічної задачі називається динамічним алгоритмом.

Багато алгоритмічних задач, що висуваються в термінах фіксованих вхідних даних (так звані статичні проблеми в цьому контексті і вирішуються статичними алгоритмами), мають значущі динамічні версії.

Спеціальні випадки

Інкрементні алгоритми або онлайн алгоритми — це алгоритми, в яких допускаються лише додавання елементів, можливо, починаючи з порожніх/тривіальних вхідних даних.

Декрементальні алгоритми є алгоритмами, в яких допускаються лише видалення елементів, починаючи з ініціалізації повної структури даних.

Якщо допускаються і видалення і додавання, алгоритм іноді називають повністю динамічним.

Приклади

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

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

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

Динамічна задача: Для початкової множини з N чисел динамічно підтримувати максимальне значення, коли допускаються операції вставки та видалення елементів.

Відоме рішення для цієї задачі є використання самозбалансованого бінарного дерева пошуку. Дерево займає O(N) пам'яті, спочатку може бути побудовано за час O (N log N) і забезпечує операції вставки, видалення та запиту з часом виконання O (log N).

Задача підтримки черги з пріоритетом: У спрощеному варіанті цієї динамічної задачі, потрібно видалити за один запит лише максимальний елемент. В такому варіанті можна опрацьовувати простіші структури даних.

Графи

Використовуючи граф, зверніть увагу на такі параметри, як зв'язність, максимальний ступінь, найкоротші шляхи і т. Д., Коли дозволяється вставляти та видаляти її краї.^[1]

Див. також

Література

↑ D. Eppstein, Z. Galil, and G. F. Italiano. «Dynamic graph algorithms». In CRC Handbook of Algorithms and Theory of Computation, Chapter 22. CRC Press, 1997.

[1] D. Eppstein, Z. Galil, and G. F. Italiano. «Dynamic graph algorithms». In CRC Handbook of Algorithms and Theory of Computation, Chapter 22. CRC Press, 1997.

[1]