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