如何用主定理求解這個遞推方程T（n）=√2T（n/2）+ log n？

Question

我知道它可以用主方法解決，但怎麼樣？請幫忙 ？

Answer 1

我不知道這是否是正確的：

a = sqrt(2) 
b = 2 
f(n) = log n 
log(b) a = log (2) sqrt(2) = 1/2 

log n in O[n^(1/2)] 

所以尋找一個數的對數n的運行時間爲O {N ^（1/2）}（但是法師定理不能應用在這裏）

的解決方案是在以下主題：Solving master theorem with log n: T(n) = 2T(n/4) + log n

總體上，我們看到你的復發是O（N1/2）和Ω（N1/2）的上限和下限的邊界重複發生越來越小的復發。因此，即使主定理不適用於此，仍然可以使用主定理來聲明運行時將爲Θ（n1/2）。

Master's theorem with f(n)=log n

通常情況下，F（N）必須是多項式的主定理應用 - 它並不適用於所有的功能。但是，對於主定理，有一個有限的「第四種情況」，它允許它適用於多對數函數。

https://en.wikipedia.org/wiki/Master_theorem

https://en.wikipedia.org/wiki/Big_O_notation

Answer 2

拉爾夫是不是告訴你正確的，你不能apply masters theorem。

這裏唯一的限制是a >=1和b >= 1，a，b可以是非理性的，f（n）可以是任何東西。

Log2(sqrt(2)) is 1/2，這會使您處於第一種情況，您的解決方案是O(n^0.5)。