我需要幫助理解在求解以下遞推關係一箇中間步驟:中間體步驟T(N)= 2T(N/2)+ N /的log(n)
通過反覆替換我已經得到了所有的方式來:
這是我在哪裏卡住了。大家都說,第二部分是等於
我已經試過很多操縱,我無法弄清楚如何到達這裏。
所以 - 兩個問題:
- 爲什麼在總和從1去的log(n)的界限?
- 你如何到達從我有序列中的這個總和?我知道該序列也被寫爲
我並不需要解決整個復發,我知道如何從那裏解決這個問題,只是這中間步驟。
我需要幫助理解在求解以下遞推關係一箇中間步驟:中間體步驟T(N)= 2T(N/2)+ N /的log(n)
通過反覆替換我已經得到了所有的方式來:
這是我在哪裏卡住了。大家都說,第二部分是等於
我已經試過很多操縱,我無法弄清楚如何到達這裏。
所以 - 兩個問題:
我並不需要解決整個復發,我知道如何從那裏解決這個問題,只是這中間步驟。
所以首先這樣的復發都解決了Master's theorem。你問爲什麼這裏是一個解釋。
第一個問題是,爲什麼你總結從1
到log n
。它很容易:你從n開始,每次減少2
次。那麼它將以多快的速度接近n
?之後log n
倍(log
意味着log2
這裏)。如果這是不明確的替代你的n
與2^k
。
現在的第二部分。你的第i個元素是(如果這些基本的操作日誌不明確的,你得重新整理你的對數的知識):
現在應該很清楚爲什麼你的解決方案是等同於他們的。
至於你對2號的回答,我對這些步驟沒有問題,我更多的是試圖理解他們爲什麼把1到1的logn相加(一個諧波序列) – user289882
我認爲這個問題更適合math.stackexchange.com。 – aschepler