algorithm - 递归关系的中间步骤 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 个元素是(如果你对这些基本的对数运算不太清楚，你得复习一下对数知识):

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