Как найти временную сложность следующего рекуррентного отношения?

Question

Время выполнения алгоритма представлено следующей рекуррентной зависимостью:

T (n) = n, если n <= 3 </h1> T (n) = T [n / 3] + cn в противном случае

Как найти временную сложность этого алгоритма?

Я получил ответ, состоящий из одного слова, биг-тэта (n).Но я не мог понять, как это найдено.Поэтому я хотел бы знать процедуру нахождения того же.

Answer 1

T(n) = cn + T(n/3)
     = cn + cn/3 + T(n/9)
     = cn + cn/3 + cn/9 + T(n/27)
Taking the sum of infinite GP series. The value of T(n) will
be less than this sum.
T(n) <= cn(1/(1-1/3))
     <= 3cn/2

or we can say 
cn <= T(n) <= 3cn/2
Therefore T(n) = \theta(n)

В противном случае: Вы также можете использовать основную теорему.

Answer 2

T (n) = T (n / 3) + cn

Или T (n / 3 ^ 2) + cn / 3 + cn

Или T (n / 3 ^3) + cn / 3 ^ 2 + cn / 3 + cn

и т. Д.

Наконец T (n) = T (n / 3 ^ k) + cn / 3 ^ (k-1) + cn / 3 ^ (k - 2) ..... cn / 3 + cn ... (1)

Базовый случай

n / 3 ^ k<= 3 или k> = log (base 3) (n / 3), для простоты рассмотрим только равенство

Таким образом, уравнение 1 станет

T (n) = n +cn / 3 ^ (k-1) + cn / 3 ^ (k - 2) ..... cn / 3 + cn

или n + cn (1 + 1/3 + 1/3 ^2 .... + 1/3 ^ (k-1), что составляет GP

или n + cn (1. (1 - 1/3 ^ (k-2)) / (1-1 /3))

Или n + cn ((3 ^ (k-1) - 3) / 2. 3 ^ (k-2))

Подстановка значения k в вышеприведенное уравнение

n + cn ((3 ^ (журнал (база 3) (n / 3 ^ 2)) / (2. 3 ^ (журнал (база 3) (n / 3 ^ 3))

, что в конечном итоге дает n + (3/2) cn

или T (n) = n (1+ (3/2) c), то есть тэта (n)

Answer 3

Может быть полезно попытаться развернуть повторение несколько раз, чтобы увидеть, какой шаблон подходит:

T [n]

= T [n / 3] + cn

= T [n / 9] + cn / 3 + cn

= T [n / 27] + cn / 9 + cn / 3 + cn

= T [n / 81] + cn / 27 + cn / 9 + cn / 3 + cn

В целом, похоже, что это повторение работает до

cn + cn/ 3 + cn / 9 + cn / 27 + cn / 81 + ...

= cn (1 + 1/3 + 1/9 + 1/27 + 1/81 + ...).

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

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