Найти сложность алгоритма?

Question

Я не смог найти сложность этого рекуррентного соотношения:

T (N) = 2T (N/4) + N^0,51

Answer 1

Использование master theorem case 3 с:

a=2, b=4, c=0.51: 

И так 2*sqrt(n/4) < 2 * (n/4)^0.51, есть k<1, что условие регулярности применяется:

2 * (n/4)^0.51 < k * n^0.51 

И так log_b(a) = log_4(2) = 0.5 < 0.51 = c

Мы можем сделать вывод, что условия теорема 3, а по теореме T(n) - i n Theta(f(n)) = Theta(n^0.51)

Answer 2

Во-первых, найти точное выражение для I-го уровня нашего периодическое отношение.

Например:

1 уровень:

2 уровень:

...

я-й уровень:

Итак, теперь мы можем выразить T(n) следующим образом:

Правая сумма геометрической прогрессии уменьшается и сложность O(1).

Из-за этого результирующая сложность O(n^0.51).