algorithm - 合并排序比较

我正在阅读Sedgewick和Flajolet的“算法分析”，在第7页Theoren 1.1给出了：
证明如下：
有人能解释O（N）去哪里吗？因为它证明了Cn是O（NlogN）。

最佳答案

你说得对；由于我无法解释的原因，他们所陈述的定理比他们实际证明的要多。这里有一种方法来填充其余的内容。
引理让n>=1的整数t（n）由定义

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

则t（n）=1的整数。
通过归纳证明对于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，对于这种情况，项（1/2）lg（1+2/（n-1））最多为1/2。（实际上，我们可以回去重新证明T（n）

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

关于algorithm - 合并排序比较，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17630184/