求解 T(n) = 7T(n/7) + n 的递归
Solve Recurrence for T(n) = 7T(n/7) + n
我正在尝试解决 T(n) = 7T(n/7) + n 的重复问题。
我知道使用 Master Theorem 是 O(nlog7n)，但我想通过替换来解决它。
在第 i 级，我得到：7^i T(n/7^i) + (n+7n+7^2n+ .... + 7^i n)
通过设置i = log7n，上面变成： 7^(log7n)*T(1) + (n + 7n + 7^2n ..... + 7^(log7n) n
由于7^log7n = n，上面最后变成了n+ (n+7n+(7^2)n+ ....n*n)
这对我来说 O(n^2) 而不是 O(nlog7n)，知道有什么问题吗？
T(n)=7T(n/7)+n=7[7T(n/72)+n/7]+n=72T(n/72)+2n=...=7kT(n/7k)+kn
n/7k=c ⇒ k=O(logn)
⇒T(n)=O(nlogn)
我正在尝试解决 T(n) = 7T(n/7) + n 的重复问题。
我知道使用 Master Theorem 是 O(nlog7n)，但我想通过替换来解决它。
在第 i 级，我得到：7^i T(n/7^i) + (n+7n+7^2n+ .... + 7^i n)
通过设置i = log7n，上面变成： 7^(log7n)*T(1) + (n + 7n + 7^2n ..... + 7^(log7n) n
由于7^log7n = n，上面最后变成了n+ (n+7n+(7^2)n+ ....n*n)
这对我来说 O(n^2) 而不是 O(nlog7n)，知道有什么问题吗？
T(n)=7T(n/7)+n=7[7T(n/72)+n/7]+n=72T(n/72)+2n=...=7kT(n/7k)+kn n/7k=c ⇒ k=O(logn) ⇒T(n)=O(nlogn)