查找溶液復發：T（N）= 2 T（N/4 +√N）+（√10）N

Question

在解決一個複雜的遞推方程這樣T(N) = 2 T(N/4 + √N) + (√10) N ;T(1) = 1

我試圖使變量的某些變化爲了使它容易，並通過大師定理解決它，但我失敗了，所以我採取占主導地位，因此它將是： T(N) = 2 T(N/4) + (√10) N所以它是T(N)=Θ(N)。這是真的還是不是？

Answer 1

試圖展開遞歸或做一個替代離開我無處。所以我唯一能做的就是看到對於任何足夠大的n（高於64）。您可以選擇任意數量（不只是8），大於4

所以你最終

解決這個與master's theorem你看，它屬於與尚屬首例。

因此解決方案是Θ(N)，這是你想知道的。