algorithm - 合并排序比较

Question

我正在阅读 Sedgewick 和 Flajolet 的“算法分析”。在第 7 页中，theoren 1.1 给出:

证明如下:

有人能解释一下 O(N) 的去向吗？因为它证明了 Cn 是 O(NlogN)。

Answer 1

你是对的；由于我无法理解的原因，他们陈述的定理比实际证明的要多。这是填写其余部分的一种方法。

引理 让整数 n >= 1 的 T(n) 定义为

T(n) = 0,                                for n = 1;
       T(floor(n/2)) + T(ceil(n/2)) + n, for n > 1.

那么对于整数 n >= 1，T(n) <= n lg n + n - 1 = n lg n + O(n)。

证明 通过归纳法。对于 n = 1，T(1) = 0 = 1 lg 1 + 1 - 1。对于 n > 1，有两种情况。如果 n 是偶数，则

T(n)  = 2T(n/2) + n
     <= 2(n/2) lg(n/2) + 2n/2 - 2 + n
      = n (lg n - 1) + 2n - 2
     <  n lg n + n - 1.

如果 n 是奇数，那么事情就变得复杂了。

T(n)  = T(n/2 - 1/2) + T(n/2 + 1/2) + n
     <=   (n/2 - 1/2) lg(n/2 - 1/2) + (n/2 - 1/2) - 1
        + (n/2 + 1/2) lg(n/2 + 1/2) + (n/2 + 1/2) - 1
        + n
      = (n/2 - 1/2) lg(n/2 - 1/2) + (n/2 + 1/2) lg(n/2 + 1/2) + 2n - 2.

这两个丑陋的项都接近于 (n/2) lg(n/2)，所以我们将每个写成该数量加上一个误差项。

T(n) <= (n/2 - 1/2) lg(n/2 - 1/2) + (n/2 + 1/2) lg(n/2 + 1/2) + 2n - 2
      =   (n/2) lg(n/2) + ((n/2 - 1/2) lg(n/2 - 1/2) - (n/2) lg(n/2))
        + (n/2) lg(n/2) + ((n/2 + 1/2) lg(n/2 + 1/2) - (n/2) lg(n/2))
        + 2n - 2
      =   n lg(n/2) + 2n - 2
        + (n/2 - 1/2) lg(n/2 - 1/2) - (n/2) lg(n/2)
        + (n/2 + 1/2) lg(n/2 + 1/2) - (n/2) lg(n/2)
      =   n (lg n - 1) + 2n - 2
        + (n/2) (lg(n/2 - 1/2) - lg(n/2)) - (1/2) lg(n/2 - 1/2)
        + (n/2) (lg(n/2 + 1/2) - lg(n/2)) + (1/2) lg(n/2 + 1/2)
      =   n lg n + n - 2
        + (n/2) lg((n/2 - 1/2)/(n/2)) - (1/2) lg(n/2 - 1/2)
        + (n/2) lg((n/2 + 1/2)/(n/2)) + (1/2) lg(n/2 + 1/2)
      =   n lg n + n - 2
        + (n/2) lg(1 - 1/n) - (1/2) lg(n/2 - 1/2)
        + (n/2) lg(1 + 1/n) + (1/2) lg(n/2 + 1/2)
      =   n lg n + n - 2
        + (n/2) lg(1 - 1/n) + (n/2) lg(1 + 1/n)
        + (1/2) lg(n/2 + 1/2) - (1/2) lg(n/2 - 1/2)
      =   n lg n + n - 2
        + (n/2) lg((1 - 1/n) (1 + 1/n))
        + (1/2) lg((n/2 + 1/2) / (n/2 - 1/2))
      =   n lg n + n - 2
        + (n/2) lg(1 - 1/n^2)
        + (1/2) lg(1 + 2/(n - 1)).

项 (n/2) lg(1 - 1/n^2) 是负数，并且对于 n >= 3，对于这种情况的最小 n，项 (1/2) lg(1 + 2/(n - 1)) 最多为 1/2。 (实际上，我们可以返回并重做证明以证明 T(n) <= n lg n + n/2 - 1/2。我将把它留作练习。)因此，

T(n) <    n lg n + n - 2
        + 0
        + 1
      = n lg n + n - 1.