最简单的应用分治策略的算法是归并排序，下面我们先给出归并排序的伪代码：

MERGE(A,p,q,r)
    n1=q-p+1
    n2=r-q
    //let L[1..n1+1] and R[1..n2+1] be new arrays
    for i=1 to n1
        L[i]=A[p+i-1]
    for j=1 to n2
        R[j]=A[q+j]
    L[n1+1]=∞
    R[n2+1]=∞
    i=1
    j=1
    for k=p to r
        if L[i]<=R[j]
            A[k]=L[i]
            i=i+1
        else
            A[k]=R[j]
            j=j+1
            
MERGE_SORT(A,p,r)
    if p<r
        q=(p+r)/2
        MERGE_SORT(A,p,q)
        MERGE_SORT(A,q+1,r)
        MERGE(A,p,q,r)

从上述伪代码我们可知，整段程序无非做了这么几件事情：

• 如果已经分解到最小颗粒n=1，那么直接返回即可，此时的时间复杂度𝛩(1)
• 如果还不是最小颗粒，那么作折半分解，也即分解为L[1..n1+1]和R[1..n2+1]后进一步递归，此时的时间复杂度为2T(n/2)；其中这里忽略了分解本身的耗时，仅统计了处理分解后排序耗时
• 针对分解后的结果作一次归并，归并过程能够在线性时间内返回，所以此时的时间复杂度为𝛩(n)

综上我们可知，归并排序的时间复杂度为：

教科书上告诉我们，归并排序的时间复杂度T(n)=𝛩(nlgn)，那么它是怎么样计算出来的呢？下面给出几种解递归式的方法。

代换法

当我们有一定编程经验之后，其实对于算法的时间复杂度分析会有一定的直觉，而且随着经验的增长这种直觉的准确性也会越来越高。所以我们不妨先假设直觉是对的，然后对其进行验证即可，这就是假设验证法的基本思想：先猜答案，再给出验证。

先来个示例：

针对这样的一个递归式，如何求其时间复杂度？

先一步，我们先猜测，猜测(1)式的时间复杂度为𝛰()。

第二步，我们验证假设。如果我们的猜测是对的，那么根据上一讲的内容，针对(1)式我们就马上有如下的结论：

于是我们对(1)式进行如下论证：

好了，现在尴尬的事情出来了，要证明上式的最终结果小于，就必须要求(-n)大于0，很显然这是不可能的。

难道我们的假设出了问题，直觉不准了？不应该呀……

问题出在(2)式上面，我们只考虑了高阶项，却忽略了低阶项对结果的影响，所以我们对(2)式进行改造，应是如下的结论：

我们应用(4)式再对(1)式进行改写，得到如下结果：

很明显，为使(5)式中的非负，只需要即可，显然这是可以的。

因此我们通过上述公式，严格论证了(1)式的时间复杂度T(n)=𝛰()针对所有的且有效。

递归树法

代换法的验证过程较为严谨，这里介绍一种我喜欢的方式，作树形图求解。一般的套路是先作图求解，而后用代换法进行验证，如果对自己比较自信的话，可以忽略验证

我们再来举个稍微复杂点的递归例子：

如何求(6)式的时间复杂度？

话不多说，直接上图说话：

image-20200129190348513.png

是不是突然感觉原来如此简单？

另外最底层为什么是𝛩(1)？因为归并算法最终分解之后都是单个元素，其时间复杂度自然是𝛩(1)

我们继续求解，如下图所示：

image-20200129190440990.png

于是我们得到这样一个等比数列：

于是问题得以求解，为求稳妥可应用代换法进行验证，此处略过。

主定理法

最后介绍一种主定理法，其根本是递归树法的应用，它有诸多限制，只能应用于形如下式的递归式上：

应用主定理，我们有三种情景：

• 当f(n)<时，T(n)=𝛩()
• 当f(n)=时，T(n)=𝛩()
• 当f(n)>，同时时，T(n)=𝛩(f(n))，原因是代价逐级递减之后，f(n)开始占主导地位

这里就不详细证明了，其实可以根据上述递归树法进行论证。其中，表示递归树中的叶节点个数，其中递归树的高度为。

应用此主定理，我们立马可以得知(1)式符合情况1，其时间复杂度T(n)=𝛩()

所以，现在大家知道为什么归并排序的时间复杂度T(n)=𝛩(nlgn)了吗？