中间体步骤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

你展现你的复发ķ时间去

这意味着N = 2 ^ķ这样：

1. 伐木的两面方程表示log（n）= log（2 ^k）= k，回答为什么绑定的总和去的log（n）
2. 替代ñ到求和的每个词，你会得到：

最后：

双方只是按相反顺序写出谐波序列彼此的。