algorithm - 求解递归：T(n)=sqrt(2)T(n/2)+log(n)

Question

给定方程T(n)=sqrt(2)T(n/2)+log(n)。

解决方案指向复杂度等级为 O(sqrt(n)) 的 MT 案例 1。然而，在我的理解之后，log(n) 是大于 sqrt(n) 的多项式。我错过了什么吗？

我使用的定义如下：n^e = log_b(a) 其中 a = sqrt(2) 和 b = 2。这将给我 e = 1/2 < 1。log n 显然是大于 n^e 的多项式。

Answer 1

编号log _x n不大于√n。

考虑n=256,

√n = 16,

和

log ₂ 256 = 8（让我们假设 base x=2，与许多计算问题一样）。

在你的复发中，

T(n)= √2 T(n/2) + log(n)
a = √2, b = 2 and f(n) = log(n)

log _b a = log ₂ √2 = 1/2。

由于log n < n ^a，对于a > 0，我们有主定理的案例 1。

那里为T(n) = Θ(√n).

Answer 2

使用大师定理，您得到：a=sqrt(2)，b = 2因此c = logb(a) = 1/2。你f(n) = log(n)，因此你属于第一种情况。

所以你的复杂性是O(sqrt(n))