Блог

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

ПРИМЕР:

 T(n) = 5T(n/2)   O(n)  T(1) =1
  

Ответ: O(n^{log_2(5)}

Расширение,

 T(n) = 5T(n/2)   cn = 5(5T(n/4)   c(n/2))   cn =



..... = 5^i * T(n/(2^i))   cn*(1   (5/2)   (5/2)^2  ......  (5/2)^i)

Now let i= log_2(n)
  

затем

 5^(log_2(n)) * T(1)   cn*(1   (5/2)   (5/2)^2  ......  (5/2)^(log_2(n)))
  

После этого я потерян. Как мне получить что-то похожее на n^{log_2(5) ?

Обновление: использование формулы для суммы геометрических рядов (сумма = a * (1-r ^ n)/(1-r))

Я получаю Sum = 1*(1-(5/2)^{log_2(n)})/(-3/2) = 2/3*c*(5^{log_2(n)} - n

Как 5^{log_2(n)} и n^{log_2(5)} связаны? Спасибо: D

Я не проверял остальную часть вашего вычисления, но обратите внимание, что

 a^b = exp(b * ln(a))
  

и

 log_b(a) = ln(a) / ln(b)
  

И, таким образом

 5^{log_2(n)} = exp(log_2(n) * ln(5)) = exp(ln(n) / ln(2) * ln(5))
  

а также

 n^{log_2(5)} = exp(ln(5) / ln(2) * ln(n))