遞歸樹
遞歸樹是迭代的圖形表示，可用于求解遞推方程。
例1：利用遞歸樹計算歸并排序的平均時間復(fù)雜度。
歸并排序偽代碼：
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); //合并兩個子數(shù)組
}
}
根據(jù)以上的偽代碼，可以寫出歸并排序的遞推方程：
其中，表示對2個子問題進行歸并排序，
表示合并2個有序的子數(shù)組的工作量（需要進行
次比較）。
假設(shè)則遞歸樹總共有k層， 則有。
舉例，假設(shè)k=3，也就是n=8，則遞歸樹有3層。
- 第一層，每個節(jié)點的工作量為8，求W(8)，對2個長度為4的有序數(shù)組進行合并，需要8-1=7次比較。
- 第二層，每個節(jié)點的工足量為4，求2個W(4)，對2個長度為2的有序數(shù)組進行合并，各需要4-1=3次比較
- 第三層，每個節(jié)點的工足量為2，求4個W(2)，對2個長度為1的有序數(shù)組進行合并，各需要2-1=1次比較，畢竟2個數(shù)比大小，1次比較就夠了。
回到一般情況，畫出遞歸樹：
上述遞歸樹共有k層，將右側(cè)的所有值相加，結(jié)合等比數(shù)列求和公式，得到：
因為，有
所以，
