好的,你很接近了。所以基本上,正如我在评论中提到的,基本情况很简单。对于归纳案例,你想证明 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 的来源。
回想起来,我应该给出关键点作为提示。我的错。对不起!