algorithm - 求解递归 T(floor[n/2]) + T(ceil[n/2]) + n - 1

Question

我有以下复发:

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 

所以它不是归并排序？我想念什么？

Answer 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 产生的差异最小。

最后是不是用代入法证明比较好

你可以证明你喜欢，有些只是更简单。越简单通常越好，但除此之外，“更好”没有任何意义。所以我的回答是否定的。