Динамическая задача (алгоритмы)
-
Определение динамических задач
- Динамические задачи — это задачи, которые требуют изменения входных данных.
- Они требуют эффективных алгоритмов и структур данных для обработки изменений в наборе входных объектов.
-
Показатели сложности
- Пространство — объем памяти, необходимый для хранения данных.
- Время инициализации — время, затрачиваемое на построение структуры данных.
- Время вставки — время, затрачиваемое на добавление нового элемента.
- Время удаления — время, затрачиваемое на удаление элемента.
- Время запроса — время, затрачиваемое на ответ на запрос.
-
Динамические алгоритмы
- Динамические алгоритмы предназначены для обработки изменений в данных.
- Они отличаются от статических алгоритмов, которые работают с фиксированными входными данными.
-
Особые случаи динамических задач
- Инкрементальные алгоритмы — разрешают только добавление элементов.
- Декрементные алгоритмы — разрешают только удаление элементов.
- Полностью динамические алгоритмы — поддерживают как добавление, так и удаление элементов.
-
Примеры динамических задач
- Задача о максимальном элементе — решается за O(N) времени с использованием бинарного дерева поиска.
- Задача о графах — сохранение параметров графа при вставке и удалении ребер.
-
Рекомендации
- Статья является заглушкой и призывает к расширению для Википедии.