【算法笔记】递归树应用实例：计算归并排序平均时间复杂度

递归树

递归树是迭代的图形表示，可用于求解递推方程。

例1：利用递归树计算归并排序的平均时间复杂度。

归并排序伪代码：

MergeSort(A,p,r)
{
    if(p<r)
    {
        q = (p+r)/2;
        MergeSort(A,p,q);
        MergeSort(A,q+1,r);
        Merge(A,p,q,r); //合并两个子数组
    }
    
}

根据以上的伪代码，可以写出归并排序的递推方程：
$W(n) = 2W(n/2) + n-1$
$W(1) = 0$
其中， $2W(n/2)$ 表示对2个子问题进行归并排序， $n-1$ 表示合并2个有序的子数组的工作量（需要进行 $n-1$ 次比较）。

假设则递归树总共有k层，则有 $n = 2^k$ 。

举例，假设k=3，也就是n=8，则递归树有3层。

第一层，每个节点的工作量为8，求W(8)，对2个长度为4的有序数组进行合并，需要8-1=7次比较。
第二层，每个节点的工足量为4，求2个W(4)，对2个长度为2的有序数组进行合并，各需要4-1=3次比较
第三层，每个节点的工足量为2，求4个W(2)，对2个长度为1的有序数组进行合并，各需要2-1=1次比较，毕竟2个数比大小，1次比较就够了。

回到一般情况，画出递归树：

上述递归树共有k层，将右侧的所有值相加，结合等比数列求和公式，得到：
$\begin{aligned} W(n) &= (n-1) + (n-2) + (n-4) +...+ (n-2^{k-1})\\ &=kn - (1+2+4+...+2^{k-1})\\ &=kn-(2^k-1) \end{aligned}$

因为 $n = 2^k$ ，有
$\begin{aligned} W(n) &= n\log_2n-n+1 \end{aligned}$
所以，
$T(n) = \Theta(n\log n)$

参考资料：https://www.icourse163.org/course/PKU-1002525003

【算法笔记】递归树应用实例：计算归并排序平均时间复杂度

递归树

推荐阅读更多精彩内容