2

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

在此处输入图像描述

证明如下：在此处输入图像描述

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

4

2 回答 2

3

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

引理令整数 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.
于 2013-07-13T15:03:55.763 回答
0

我不确定您所询问的 O(N) 究竟在哪里是错误的或缺失的，但他们的分析对于特殊情况很好N = 2^n。

(1) 之后的第一行数学只是重新陈述了特殊情况的递归。接下来，一长串数学节目

C_{2^n} = (2^n) n

现在我们知道2^n = N了等等n = lg N。用这两个替换我们得到

C_N = N lg N

正如他们所说。如果我没有正确看到您的问题，请发表评论。

于 2013-07-13T16:51:01.903 回答