algorithm - 给出递归的上限 T(n) = T(floor(n/2)) + n

Question

我能够正确得到 O(nlogn)。但我也认为 O(n) 会起作用，除了 here它提到 O(n) 是错误的，因为“错误是我们还没有证明归纳假设的确切形式:T(n) <= cn”。我不确定那是什么意思。

这是我的做法:

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

Answer 1

“错误在于我们还没有证明归纳假设的确切形式:T(n) <= cn。” 意思如下:

你从猜测开始:

T(n) <= cn

你最终会得到这个:

T(n) <= cn + n

但这不是您可以用来证明您的猜测的东西。换句话说，这个暗示是不正确的:

T(n) <= cn + n ⟹ T(n) <= cn

然而，这正是您要使证明听起来合理的原因。你可以说，好吧，我将从这个猜测开始:

T(n) <= (c+1)n

但是你总是会得到更大的表达式，这并不意味着你的猜测。