关于归并排序时间复杂度 T（n） =2T（n/2）+O（n）

Question

T（n）=2T（n/2）+O（n），n=2^k。
想知道为什么最终答案为O（nlgn）

Answer 1

Master大法好。这题自己推导也不难。把递推公式重复代入三次并化简：

$$\array{\text{1}:&T(n)<2\ T(\frac{n}{2})+ c\ n\\\ \text{2:}&\ \ T(n)<4\ T(\frac{n}{4})+ 2\ c\ n\\\ \text{3:}&\ \ T(n)<8\ T(\frac{n}{8})+ 3\ c\ n}$$

可以看出规律了，而且很容易用归纳法证明。于是代入$k$次时就有（$n=2^k$）：

$$\array{\qquad\text{k}:&T(n)<2^k\ T(\frac{n}{2^k})+ k\ c\ n\\&\quad\ \qquad=n\ T(1) + c\ n\ \log_2{n}\\&=\Theta(n\log{n})}$$

Answer 2

您好, 这要用到主定理(master theorem)来证明, 是第四章递归式开篇介绍的方法, 并且其引入的例子就是你提问的这个式子, 具体解法和原理你可以去看原书, 讲解的非常详细. 也可以去这个网站上下算法导论课(与书同名, 是清华姚班的罗辑写的课), 里面第二章也介绍了主定理的证明和应用, 不懂的地方提问后罗辑本人也会回答你. coursera上也有主定理的证明

---

其实这个复杂度你也可以抛开详细的数学推导, 直接用分治的思想来考虑, 很容易想到, 其实你一共需要$O(log n)$层归并操作, 每一层归并操作的时间复杂度都是$O(n)$, 所以这个算法的时间复杂度是$O(n log n)$.

   void merge_sort(int l, int r)
    {
        if (l == r)
        {
            return;
        }
        int mid = (l + r) / 2;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
        int x = l, y = mid + 1, loc = l;
        while (x <= mid || y <= r)
        {
            if (x <= mid && (y > r || data[x] <= data[y]))
            {
                temp[loc] = data[x];
                x++;
            }
            else
            {
                temp[loc] = data[y];
                y++;
            }
            loc++;
        }
        for (int i = l; i <= r; i++)
        {
            data[i] = temp[i];
        }
    }

代码部分引自计蒜客

Answer 3

T(n) = 2T(n/2)+O(n)
= 2(2T(n/4)+O(n/2))+O(n)
= 2(2(2T(n/8)+O(n/4))+O(n/2))+O(n) = 8T(n/8)+[4O(n/4)+2O(n/2)+O(n)] 
n = 2^k 
[ ] = n*lgn
2^kT(n/2^k) = cn
T(n) = n*lgn + cn = n*lgn