用主定理求解 4T(n/5) + log5(n * sqrt(n))
Solving 4T(n/5) + log5(n * sqrt(n)) with the master theorem
我正在尝试用主定理求解递归 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？我不明白如何进行。谢谢
log(n * sqrt(n)) = log(n^{1.5}) = 1.5* log(n)
这样你的公式就变成了
T(n) = 4T(n/5) + 1.5 * log5(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？我不明白如何进行。谢谢
log(n * sqrt(n)) = log(n^{1.5}) = 1.5* log(n)
这样你的公式就变成了
T(n) = 4T(n/5) + 1.5 * log5(n)