Первое рекуррентное отношение: алгоритм сортировки слиянием
Чтобы понять общий подход к анализу алгоритмов «разделяй и властвуй», начнем с алгоритма сортировки слиянием.
Чтобы проанализировать время выполнения сортировки слиянием, мы абстрагируем поведение алгоритма в следующий шаблон, описывающий многие типичные алгоритмы «разделяй и властвуй».
(†) Разбить входные данные на два блока равного размера; рекурсивно решить две подзадачи для этих блоков по отдельности; объединить два результата в одно решение, с линейными затратами времени для исходного деления и итогового объединения.
В алгоритме сортировки слиянием, как и в любом алгоритме этого типа, также необходим базовый случай рекурсии, который обычно завершает выполнение для входных данных некоторого постоянного размера.
В случае сортировки слиянием предполагается, что при достижении размера 2 рекурсия останавливается, а два элемента сортируются простым сравнением.
Рассмотрим любой алгоритм, построенный по шаблону (†); обозначим T(n) худ- шее время выполнения для входных данных с размером n.
Если предположить, что n четно, алгоритм за время O(n) делит входные данные на два блока с размером n/2, а затем тратит время T(n/2) на решение каждой производной задачи (T(n/2) — худшее время выполнения для входных данных с размером n/2); и наконец, время O(n) тратится на объединение решений из двух рекурсивных вызовов.
Это время выполнения T(n) удовлетворяет следующему рекуррентному отношению.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу