Нахождение рекуррентных соотношений алгоритма
Я читаю свой учебник алгоритмов, и я читаю о рекуррентных соотношениях и нахожу алгоритмы большой сложностью O. Я натыкаюсь на эту строку
"In the case of the merge-sort algorithm, we get the recurrence equation:
t(n) = b if n < 2
= 2t(n/2) +bn if n >= 2
for b > 0
мой ответ был "как, черт возьми, мы знали это?!?!"
Таким образом, я задаюсь вопросом, существует ли систематический подход или просто логический способ получить эти рекуррентные соотношения из алгоритмов
кто-то может объяснить, куда b и два 2's прибывают из?
3 ответа
Алгоритм сортировки слиянием можно резюмировать следующим образом:
mergesort (array A) {
mergesort (first half of A);
mergesort (second half of A);
merge the two halves and return;
}
Существует алгоритм O (N) для объединения двух массивов длины N, то есть его сложность составляет bN для некоторой константы b > 0.
Предполагая, что сложность сортировки слиянием равна T (N). Поскольку половина N равна N / 2, мы видим, что:
mergesort (array A) { T(N) =
mergesort (first half of A); T(N/2) +
mergesort (second half of A); T(N/2) +
merge the two halves and return; bN
}
, что объясняет случай N ≥ 2.
Случай N <2 (базовый случай, когда вы останавливаете рекурсию) тривиален.
Что ж, это утверждение является (предположительно) заключением обсуждения или, по крайней мере, утверждением рассматриваемого алгоритма. Без подробностей я могу делать только обоснованные предположения, которые выглядели бы следующим образом:
- первое, что делает алгоритм, это проверяет, просят ли его обработать 0 или 1 элемент. Если это правда, он немедленно возвращается. Таким образом, тогда
n <2, существует фиксированная стоимость - назовем ееb - Для
n> = 2алгоритм разбивает входные данные на две части, каждая размеромn / 2, и вызывает себя на каждой части. Каждый такой вызов будет иметь стоимостьt (n / 2), и есть два таких вызова - Затем будет дополнительная стоимость для объединения двух частей вместе - эта стоимость будет пропорциональна
n- назовем этоbразn
Единственная небольшая странность состоит в том, что не совсем очевидно, почему возникающие два постоянных фактора должны быть одинаковыми - но часть Суть анализа большого числа в том, что постоянные факторы в конечном итоге не имеют значения.
T(n) = c if n < d
= A*T(n/b) + f(n)
где d> = 1 и есть подзадачи A, а размер подзадач не превышает n / b. f (n) - общее дополнительное время, необходимое для разделения проблемы на подзадачи и объединения решений подзадач в решение всей проблемы.
это для алгоритмов «разделяй и властвуй».
Интересно, почему в сортировке слиянием есть две подзадачи?