我正在尝试求解 T(n) = 7T(n/7) + n 的递归式。
我知道使用主定理它是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)
关于recurrence - 求解 T(n) = 7T(n/7) + n 的递归，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/63947037/