Поиск рекуррентных отношений алгоритма

Question

Я читаю текстовые книги с алгоритмами, и я читаю о рекуррентных отношениях и нахождении алгоритмов большой сложности 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 

Мой ответ был «как, черт возьми, мы знаем это?!?!»

Так что я интересно, если есть системный подход, или просто логический способ получить эти рекуррентные соотношения из алгоритмов

может кто-нибудь объяснить, где б и два 2-х пришли?

Answer 1

Алгоритм сортировка слиянием можно резюмировать следующим образом:

mergesort (array A) { 
    mergesort (first half of A); 
    mergesort (second half of A); 
    merge the two halves and return; 
} 

Существует уплотнительное алгоритм (N), чтобы слияния двух массивов длины N, то есть ее сложность Bn для некоторой постоянной б> 0.

Предполагая, что сложность mergesort равна 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 случай (базовый кейс, где вы останавливаете рекурсию) является тривиальным.

Answer 2

Ну, это утверждение является (предположительно) завершением обсуждения или, по крайней мере, утверждением рассматриваемого алгоритма. Без подробностей я могу только дать обоснованные догадки, которые бы прошли следующим образом:

• Первое, что делает алгоритм, это проверить, требуется ли ему обрабатывать 0 или 1 элемент. Если это правда, оно немедленно возвращается. Таким образом, тогда n < 2, существует фиксированная стоимость - назовите ее b
• Для n >= 2 алгоритм разбивает свой ввод на две части, каждый из которых имеет размер n/2 и вызывает себя на каждой части. Каждый такой вызов будет иметь стоимость t(n/2), и есть две таких вызовов
• Существуют то дополнительные расходы, чтобы объединить две части вместе - это стоимость будет пропорциональна n - назовет это b раз n

Единственная незначительная странность заключается в том, что не совсем очевидно, почему два постоянных фактора, которые возникают, должны быть одинаковыми, но часть точки анализа большого вывода состоит в том, что постоянные факторы в конечном итоге не имеют значения.

Answer 3

T(n) = c if n < d 
    = A*T(n/b) + f(n) 

где d> = 1 и есть подзапросы, а подзадачи не более n/b. f (n) - общее дополнительное время, необходимое для деления задачи на подзадачи и объединения решений подзадач в решение всей задачи.

Это для алгоритмов разделения и покорения.

Интересно, почему существует 2 подзадачи в сортировке слияний?