algorithm - 问：求解以下递归：T(n) = 8T(n/8) + n log n

Question

我正在尝试解决以下重复问题：

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).

我不知道如何继续这个。我试图重写logas n^k / 8^(k*(k+1)/2)，但我仍然没有看到解决方案。

标签： algorithmdata-structurestime-complexity

Answer 1

你快到了。设置k = log_8(n)然后你可以解决T(n)