中間體步驟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. 替代ñ到求和的每個詞，你會得到：

最後：

雙方只是按相反順序寫出諧波序列彼此的。