Решение 4T(n/5) + log5(n * sqrt(n)) с помощью основной теоремы

Я пытаюсь решить рекурсию 4T (n/5) + log5 (n * sqrt (n)) с помощью основной теоремы, но столкнулся с некоторыми трудностями.

Я понимаю, что использование формы T(n) = a T(n/b) + theta(n^k log^p n) даст:

a = 4
b = 5
k = 0

но как мне справиться с n * sqrt n в журнале? Я не могу понять, как поступить. Спасибо


recurrence algorithm math master-theorem
person Niblink    schedule 10.02.2021    source источник
comment
Продумайте журнальные тождества. Есть способ преобразовать его в форму, которую вы показали.   -  person Arya McCarthy    schedule 10.02.2021
comment
Я голосую за то, чтобы закрыть этот вопрос, потому что вы должны задать его на math.stackexchange.com, а не здесь.   -  person Peter O.    schedule 10.02.2021
comment
@AryaMcCarthy Я попробую, спасибо!   -  person Niblink    schedule 10.02.2021
comment
@ПитерО. Это относится к нотации O программных алгоритмов, но я вижу вашу точку зрения, я бы сказал, что это не повредит.   -  person Niblink    schedule 10.02.2021
comment
Алгоритмический анализ очень актуален здесь. Если бы был существовал второй сайт, на котором он должен быть, cs.se, вероятно, был бы более подходящим, чем math.se.   -  person ggorlen    schedule 21.02.2021

Ответы (1)


arrow_upward
1
arrow_downward

log(n * sqrt(n)) = log(n^{1.5}) = 1.5* log(n)

таким образом, ваша формула становится T(n) = 4T(n/5) + 1.5 * log5(n)

person Bob    schedule 10.02.2021
comment
А, я не уловил ту логарифмическую идентичность с силой n. Большое спасибо за Вашу помощь! - person Niblink; 10.02.2021