查找THETA：T（N）= T（N ^（1/2））+ 1

Question

我嘗試這樣做許多小時和我保持到達日誌（logn）時間（其中log爲基數爲2），但這並不同意保持它只是log（n）的大師定理。

Answer 1

碩士定理在這裏並不適用，因爲我們沒有除以常數輸入的每一步。你的回答是正確的。

Answer 2

爲了施加主定理，我們必須通過在每個步驟中的常數來劃分。在這種情況下，我們仍然可以使用它，但我們必須改變這個問題。

令k=log n，其中對數爲基數b，並且定義爲S(k)=T(b^k)。然後S(k)=T(b^k)=T(n)=T(n^{1/2})+1=T((b^k)^{1/2})+1=T(b^{k/2})+1=S(k/2)+1，我們可以應用主定理S，它告訴我們S(k)=Theta(log k)。因此，您發現T(n)=T(b^{log n})=S(log n)=Theta(log(log n))。

Answer 3

人們正確地建議你，主人定理在這裏不起作用。 要解決您的問題，您必須開始展開遞歸：。

遞歸將在某個時間點停止，所以我們必須找到一個合理的停止點。嘗試0,1,2，你可以看到2看起來不錯，因爲你可以很容易的解出方程：。

解決它，你會得到。

所以遞歸將繼續log(log(n))次，這是你的時間複雜度。

附：有點難度的復發被解決了here。