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

递归树

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

例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); //合并两个子数组
    }
    
}

根据以上的伪代码，可以写出归并排序的递推方程：


其中，表示对2个子问题进行归并排序，表示合并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层，将右侧的所有值相加，结合等比数列求和公式，得到：

因为，有

所以，

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