1

我想证明 T(n)=T(n/2)+sqrt(n) 是 O(sqrt(n)) 给定 T(1)=1 仅使用归纳法。使用 Master 定理很容易解决，但事实并非如此。我试图假设

T(n/2) < c*sqrt(n/2)

但在其余的证明中并没有走得太远。预先感谢大家的回答。

编辑：我的解决方案（在上述假设之后）是：

T(n) <= c*sqrt(n/2)+sqrt(n) = sqrt(n) (c/sqrt(2)+1) <= sqrt(n) (c+1)

我不知道如何从这个转移到所需的

T(n)<=c*sqrt(n)

4

2 回答 2

3

好的，你很接近了。所以基本上，正如我在评论中提到的，基本情况很简单。对于归纳案例，你想证明 T(n) 是 O(sqrt(n))，因为 T(n/2) 是 O(sqrt(n/2))。

所以，它是这样的：

T(n) = T(n/2) + sqrt(n)               ; this is just your recurrence
     < c sqrt(n/2) + sqrt(n)          ; since T(n/2) is O(sqrt(n))
                                      ; wlog here, assume c > 4
     = c sqrt(n) / sqrt(2) + sqrt(n)
     = (c/sqrt(2) + 1) sqrt(n)

观察对于 c > 4，c / sqrt(2) + 1 < c，所以

(c/sqrt(2) + 1) sqrt(n) < c sqrt(n)

所以

T(n) < c sqrt(n)

因此，T(n) 为 O(sqrt(n))

所以这里有几个关键点你错过了。

首先是您可以随时将 c 增加到您想要的任何值。这是因为大 O 只需要 <. 如果它是 < cf(n) 那么它是 < df(n) 其中 d > c。

第二个是注意线 f(c) = c/sqrt(2) + 1 与线 f(c) = c 相交大约在 c = sqrt(2) / (sqrt(2)-1) = 3.4143 （或如此），所以你所要做的就是强制 c > 这个值以获得 (c/sqrt(2) + 1) < c。4 确实有效，所以这就是 4 的来源。

回想起来，我应该给出关键点作为提示。我的错。对不起！

于 2013-01-28T22:56:30.767 回答
1

一种可能有帮助的思路是递归地扩展递归。你得到

T(n) = sqrt(n) + sqrt(n/2) + sqrt(n/4) + ... + sqrt(n/(2^k)) + ... + sqrt(1)
     = sqrt(n) + sqrt(n)/sqrt(2) + sqrt(n)/sqrt(4) + ... + sqrt(n)/sqrt(2^k) + ... + sqrt(1)
     = sqrt(n) * (1 + sqrt(1/2) + sqrt(1/2)^2 + ... + sqrt(1/2)^k + ...)
     <= sqrt(n) * ∑(k=0 to ∞) sqrt(1/2)^k
     = sqrt(n) * 1/(1 - sqrt(1/2))

由于1/(1-sqrt(1/2))是一个有限常数（大约为 3.4），T(n)因此必须是O(sqrt(n)). 您可以使用此信息使用标准归纳来证明它。

于 2013-01-28T23:20:20.630 回答