使用替换找出 T(1) = 1 的 运行 时间； T(n) = 4T(n/3) + n
Use substitution to find out the running time of T(1) = 1 ; T(n) = 4T(n/3) + n
我已经达到了 4^logn + 3n[(4/3)^logn -1] 并且无法完成它。
对数以 3 为底。（不确定如何计算下标和指数。）
谢谢。
这是使用大师定理的最佳地点。在您的情况下，我们希望以
的形式编写重复
T(n) = aT(n / b) + O(nd).
随着你的复发，你得到
- 一个=4
- b = 3
- c = 1
因为 logba > d，Master Theorem 说这解决了 O(nlog3 4).
希望对您有所帮助！
Masters 定理是解决这类问题的通用工具，但如果你想通过代换得到具体的解决方案，那么它如下：
T(n) = 4T(n/3) + n
T(n) = 4(4T(n/9) + n/3) + n = 4^2T(n/9) + (4/3)n + n
T(n) = 4^2(4T(n/27) + n/3^2) + (4/3)n + n = 4^3T(n/27) + (4/3)^2n + (4/3)n + n
T(n) = 4^kT(n/3^k) + (4/3)^(k-1)n + (4/3)^(k-2)n....
boundary condition
n/3^k = 1, k = log3(n)
T(1) = 1
geometric series summation
T(n) = 4^log3(n) + 1((4/3)^log3(n) - 1)/(log3(n)-1)*n
using log rules
T(n) = n^(log3(4)) + n^(1+log3(4/3))/(log3(n)-1) - n/(log3(n)-1)
T(n) = n^(log3(4)) + n^(1+log3(4)-log(3))/(log3(n)-1) - n/(log3(n)-1)
T(n) = n^(log3(4)) + n^(log3(4))/(log3(n)-1) - n/(log3(n)-1)
T(n) = O(n^log3(4))
我已经达到了 4^logn + 3n[(4/3)^logn -1] 并且无法完成它。
对数以 3 为底。（不确定如何计算下标和指数。）
谢谢。
这是使用大师定理的最佳地点。在您的情况下，我们希望以
的形式编写重复T(n) = aT(n / b) + O(nd).
随着你的复发，你得到
- 一个=4
- b = 3
- c = 1
因为 logba > d，Master Theorem 说这解决了 O(nlog3 4).
希望对您有所帮助！
Masters 定理是解决这类问题的通用工具，但如果你想通过代换得到具体的解决方案，那么它如下：
T(n) = 4T(n/3) + n
T(n) = 4(4T(n/9) + n/3) + n = 4^2T(n/9) + (4/3)n + n
T(n) = 4^2(4T(n/27) + n/3^2) + (4/3)n + n = 4^3T(n/27) + (4/3)^2n + (4/3)n + n
T(n) = 4^kT(n/3^k) + (4/3)^(k-1)n + (4/3)^(k-2)n....
boundary condition
n/3^k = 1, k = log3(n)
T(1) = 1
geometric series summation
T(n) = 4^log3(n) + 1((4/3)^log3(n) - 1)/(log3(n)-1)*n
using log rules
T(n) = n^(log3(4)) + n^(1+log3(4/3))/(log3(n)-1) - n/(log3(n)-1)
T(n) = n^(log3(4)) + n^(1+log3(4)-log(3))/(log3(n)-1) - n/(log3(n)-1)
T(n) = n^(log3(4)) + n^(log3(4))/(log3(n)-1) - n/(log3(n)-1)
T(n) = O(n^log3(4))