我正在尝试解决以下重复问题:
T(n) = 8T(n/8) + n* log n.
我目前已完成以下操作,但不确定我是否在正确的轨道上:
1. T(n)= 8 T(n/8) + n log n;
2. T(n)= 8^2 T(n/8^2) + n log (n/8) + n log n
3. T(n)= 8^3 T(n/8^3) + n log (n/8^2) + n log (n/8) + n log n
所以我想到了一般公式:
T(n)= 8^k T(n/8^k) + n log(n* n/8 * n/8^2 * ... * n/8^k).
而且我不确定如何继续这个。我试图将 log
重写为
n^k/8^(k*(k+1)/2)
,但我仍然没有看到解决方案。
最佳答案
你快到了。设置 k = log_8(n)
然后你可以解决 T(n)
关于algorithm - Q : Solving the following recurrence: T(n) = 8T(n/8) + n log n,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53344868/