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

递归树

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

例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(n)=2W(n/2)+n−1
$W(1) = 0$W(1)=0
其中，$2W(n/2)$2W(n/2)表示对2个子问题进行归并排序，$n-1$n−1表示合并2个有序的子数组的工作量（需要进行$n-1$n−1次比较）。

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

举例，假设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}$W(n)​=(n−1)+(n−2)+(n−4)+...+(n−2k−1)=kn−(1+2+4+...+2k−1)=kn−(2k−1)​

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

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