Нахождение рекуррентных соотношений алгоритма - PullRequest
Новая
       28

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

1 голос
/ 27 мая 2010

Я читаю учебник по моим алгоритмам и читаю о рекуррентных соотношениях и нахожу алгоритмы большой сложности. Я пересекаю эту строку 

"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?

Ответы [ 3 ]

1 голос
/ 27 мая 2010

Алгоритм сортировки слиянием можно суммировать как: 

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.

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

1 голос
/ 27 мая 2010

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

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

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

0 голосов
/ 27 мая 2010 
T(n) = c if n < d
     = A*T(n/b) + f(n)

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

это для алгоритмов разделяй и властвуй.

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

...