平方根下面的遞推關係的解是什麼：T（n）= T（[√n]）+ logn？

-1

我知道有一個類似於這個的問題，但那是+1。我想知道如果我們在那裏有對數函數，我們將如何進行？我覺得你會嘗試進行基本情況，T（n^1/2^k）+ log（n ^（（2^k-1）/（2^k-2^k- 1））平方根下面的遞推關係的解是什麼：T（n）= T（[√n]）+ logn？

但你在這之後做

2017-05-04 coder123

我正在投票結束因爲這似乎是關於數學，而不是編程。 – Chris

你可能想檢查一下，看看這個話題是否在https://math.stackexchange.com/這是一個數學堆棧交換站點，因此與這個問題更相關。 – Chris

努力擴大復發什麼：？

T(n) = T(n^0.5) + log(n) = 
    = T(n^0.25) + log(n^0.5) + log(n) = 
    = T(n^0.25) + 0.5 log(n) + log(n) = 
    = ...

所以另一種形式來寫這個循環將

(1 + 0.5 + 0.25 + ...) * log(n) = 2 log(n)

2017-05-04 14:06:00 Paul

回答