给出递归的上限 T(n) = T(floor(n/2)) + n
Giving an upper bound for the recurrance T(n) = T(floor(n/2)) + n
我能够正确地得到 O(nlogn)。但我也认为 O(n) 会起作用，除了 here 它提到 O(n) 是错误的，因为 "The error is that we haven't proved the exact form of the inductive hypothesis: T(n) <= cn." 我不确定那是什么意思。
我就是这样做的：
T(n) <= cn
T(n) <= 2c*floor(n/2) + n
T(n) <= 2c*n/2 + n
cn <= n(c + 1)
"The error is that we haven't proved the exact form of the inductive hypothesis: T(n) <= cn."表示如下：
你从猜测开始：
T(n) <= cn
你最终得到这个：
T(n) <= cn + n
但这不是你可以用来证明你的猜测的东西。换句话说，这个含义是不正确的：
T(n) <= cn + n ⟹ T(n) <= cn
然而，这正是您要使证明听起来合理的原因。你可以说，好吧，我将从这个猜测开始：
T(n) <= (c+1)n
但是你总是会得到更大的表达式，这并不意味着你的猜测。
我能够正确地得到 O(nlogn)。但我也认为 O(n) 会起作用，除了 here 它提到 O(n) 是错误的，因为 "The error is that we haven't proved the exact form of the inductive hypothesis: T(n) <= cn." 我不确定那是什么意思。
我就是这样做的：
T(n) <= cn
T(n) <= 2c*floor(n/2) + n
T(n) <= 2c*n/2 + n
cn <= n(c + 1)
"The error is that we haven't proved the exact form of the inductive hypothesis: T(n) <= cn."表示如下：
你从猜测开始：
T(n) <= cn
你最终得到这个：
T(n) <= cn + n
但这不是你可以用来证明你的猜测的东西。换句话说，这个含义是不正确的：
T(n) <= cn + n ⟹ T(n) <= cn
然而，这正是您要使证明听起来合理的原因。你可以说，好吧，我将从这个猜测开始：
T(n) <= (c+1)n
但是你总是会得到更大的表达式，这并不意味着你的猜测。