Найти рецидивных отношений алгоритма

StackOverflow https://stackoverflow.com/questions/2919698

  •  05-10-2019
  •  | 
  •  

Вопрос

Я читаю свои алгоритмы текстовой книги, и я читаю о рецидивов отношениях и нахожу алгоритмы Big o Colotoity. Я бегу через эту линию 

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

Это было полезно?

Решение

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

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

Существует алгоритм O (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 случай.

Case N <2 (базовый случай, когда вы остановите рекурсию), тривиально.

Другие советы

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top