递归关系的中间步骤 T(n) = 2T(n/2)+ n/log(n)

Question

我需要帮助理解解决以下递归关系的一个中间步骤：

通过反复替换我已经达到了：

这就是我卡住的地方。大家都说第二部分等于

我已经尝试了很多操作，但我不知道如何到达这里。

所以 - 两个问题：

1. 为什么总和的界限从 1 到 log(n)？
2. 你是如何从我的序列得出这个总和的？我知道序列也写成

我不需要整个循环的解决方案，我知道如何从那里解决它，只是这个中间步骤。

Answer 1

因此，首先使用 Master's theorem 解决此类重复问题。你问为什么，这里有一个解释。

第一个问题是为什么要从 1 求和到 log n。很简单：您从数字 n 开始，每次将其减少 2 次。那么它将以多快的速度接近n？在 log n 次之后（log 在这里表示 log2）。如果不清楚，请将 n 替换为 2^k。

现在是第二部分。你的第i个元素是（如果这些基本的对数运算你还不清楚，你得温习一下对数知识）：

现在应该清楚为什么你的解决方案与他们的解决方案等同了。

Answer 2

您已展开 k 次循环以到达

这意味着 n = 2^k 所以：

1. 记录这个等式的两边意味着 log(n) = log(2^k) = k 这回答了为什么求和边界转到 log(n)
2. 将 n 代入求和的每一项，得到：

最后：

双方只是互逆顺序写调和级数。