通過替代解決遞推方程

Question

我試圖通過繪製再恢復樹來解決T(n) = sqrt(n)*T(sqrt(n))+sqrt(n)並解決它是替代方法。但是我很難包圍我的頭，因爲sqrt方法將如何影響這個過程，並且我正在尋找一些可能的指針

非常感謝！

Answer 1

你可以寫T(n) = sqrt(n)⋅T(sqrt(n)) + sqrt(n)作爲

T(n) = n1/2 + n3/4 + n7/8 + ... 

我們知道Σi=1,...,∞ 2-i = 1，所以可以說

 
T(n) = n1/2 + n3/4 + n7/8 + ... < n + n + n + ... 

現在您只需通過解決n2-x < 2計算總和的長度和你喜歡的東西x ≈ log log n。

所以解決方案是T(n) = O(n ⋅ log log n)。

對不起，您正在尋找使用substitun方法的解決方案。我從來沒有這樣做過，所以我讀了this site的描述。

讓T(sqrt(n)) = k ⋅ sqrt(n) ⋅ log log sqrt(n) + O(sqrt(n))爲常數k。

T(n) = sqrt(n) ⋅ k ⋅ sqrt(n) ⋅ log log sqrt(n) + sqrt(n) + O(sqrt(n)) 
    = k ⋅ n ⋅ log (0.5 log n) + sqrt(n) + O(sqrt(n)) 
    = k ⋅ n ⋅ log log n + log 0.5 + sqrt(n) + O(sqrt(n)) 
    = k ⋅ n ⋅ log log n + O(sqrt(n)) 
    = O(n log log n) 

我希望這會有所幫助。