求解递归 T(floor[n/2]) + T(ceil[n/2]) + n - 1
solving the recurrence T(floor[n/2]) + T(ceil[n/2]) + n - 1
我有以下复发：
T(n) = c for n = 1.
T(n) = T(floor[n/2]) + T(ceil[n/2]) + n - 1 for n > 1.
对我来说它看起来像归并排序，所以我猜递归的解是 Θ(nlogn)。根据大师的方法我有：
a) Θ(1) for n = 1 (constant time).
b) If we drop the floor and ceil we have: (step1)
T(N) = 2T(N/2) + n - 1 => a = 2, b = 2.
logb(a) (base b) = lg(2) = 1 so n^lg(2) = n^1 = n
仔细看看我们知道我们有master方法的情况2：
if f(n) = Θ(log(b)a) our solution to the recurrence is T(n) = Θ(log(b)a log(2)n)
解决方案确实是 T(n) = Θ(nlogn) 但我们偏离了常数因子 1。
我的第一个问题是：
在第 1 步，我们去掉了 ceil 和 floor。这个对吗 ？第二个问题是如何去掉常数因子 1？我放下它吗？或者我应该将它命名为 d 并证明 n - 1 确实是 n （如果是这样我如何证明它？）。最后用替换法证明是不是更好？
编辑：如果我们使用替换方法，我们得到：
We guess that the solution is O(n). We need to show that T(n) <= cn.
Substitutting in the recurrence we obtein
T(n) <= c(floor[n/2]) + c(ceil[n/2]) + n/2 - 1 = cn + n/2 - 1
所以这不是归并排序？我想念什么？
这是很久以前的事了，现在是
第 1 步我们去掉了天花板和地板。这是正确的吗？
我宁愿说
T(floor(n/2)) + T(floor[n/2)) <= T(floor(n/2)) + T(ceil[n/2))
T(floor(n/2)) + T(ceil[n/2)) <= T(ceil(n/2)) + T(ceil[n/2))
如果它们不相等，则相差 1（您可以忽略任何常量）
第二个问题是如何去掉常数因子 1？
你无视它。其背后的原因是：即使常数很大 10^100，与 n 变大时的大小相比，它也会很小。在现实生活中，你不能真正忽略非常大的常数，但这就是现实生活和理论的不同之处。在任何情况下，1 的差异最小。
最后是不是用代入法证明比较好
你可以证明你喜欢什么，有些只是更简单。通常越简单越好，但除此之外 'better' 没有任何意义。所以我的回答是否定的。
我有以下复发：
T(n) = c for n = 1.
T(n) = T(floor[n/2]) + T(ceil[n/2]) + n - 1 for n > 1.
对我来说它看起来像归并排序，所以我猜递归的解是 Θ(nlogn)。根据大师的方法我有：
a) Θ(1) for n = 1 (constant time).
b) If we drop the floor and ceil we have: (step1)
T(N) = 2T(N/2) + n - 1 => a = 2, b = 2.
logb(a) (base b) = lg(2) = 1 so n^lg(2) = n^1 = n
仔细看看我们知道我们有master方法的情况2：
if f(n) = Θ(log(b)a) our solution to the recurrence is T(n) = Θ(log(b)a log(2)n)
解决方案确实是 T(n) = Θ(nlogn) 但我们偏离了常数因子 1。 我的第一个问题是： 在第 1 步，我们去掉了 ceil 和 floor。这个对吗 ？第二个问题是如何去掉常数因子 1？我放下它吗？或者我应该将它命名为 d 并证明 n - 1 确实是 n （如果是这样我如何证明它？）。最后用替换法证明是不是更好？
编辑：如果我们使用替换方法，我们得到：
We guess that the solution is O(n). We need to show that T(n) <= cn.
Substitutting in the recurrence we obtein
T(n) <= c(floor[n/2]) + c(ceil[n/2]) + n/2 - 1 = cn + n/2 - 1
所以这不是归并排序？我想念什么？
这是很久以前的事了，现在是
第 1 步我们去掉了天花板和地板。这是正确的吗？
我宁愿说
T(floor(n/2)) + T(floor[n/2)) <= T(floor(n/2)) + T(ceil[n/2))
T(floor(n/2)) + T(ceil[n/2)) <= T(ceil(n/2)) + T(ceil[n/2))
如果它们不相等，则相差 1（您可以忽略任何常量）
第二个问题是如何去掉常数因子 1？
你无视它。其背后的原因是：即使常数很大 10^100，与 n 变大时的大小相比，它也会很小。在现实生活中，你不能真正忽略非常大的常数，但这就是现实生活和理论的不同之处。在任何情况下，1 的差异最小。
最后是不是用代入法证明比较好
你可以证明你喜欢什么，有些只是更简单。通常越简单越好，但除此之外 'better' 没有任何意义。所以我的回答是否定的。