該樹結(jié)構(gòu)顯示了從1(根節(jié)點)到n(n個葉節(jié)點)的整個倍增過程。節(jié)點下的標簽表示從n減半到1的過程。

　　當我們處理遞歸的時候，這些級數(shù)代表了問題實例的數(shù)量以及對一系列遞歸調(diào)用來說處理的相關工作量。

　　當我們需要找出全部的工作量時，我們需要用到樹的高度以及每一層所處理的工作量。每一層總共的標志總數(shù)保持在n。

Recursion and Recurrences

　　該求和式從參數(shù)i開始，當其值超出目標序列時，函數(shù)返回0；否則將i的位置加i，繼續(xù)求剩下序列的和。

　　計算 S(seq，i) 所需要的時間T(n)等于遞歸調(diào)用 S(seq，i+1) 所需要的時間加上訪問 seq[i] 所需的時間。(默認T(k) = Θ(1) , k為常數(shù))

　　可以定義為 T(n) = T(n-1) + 1

　　目標是把遞歸展開的層數(shù)用一個變量i來描述的表達式。

　　將原式中的n值替換為n-1可得 : T(n-1) = T(n-2) + 1

　　假設T(n)遞歸展開式次數(shù)為i，可得：

　　T(n) = T(n-i) + i

　　然后將T(n-i) 變成 T(i)

　　所以，函數(shù)S是一個線性級的運行時間的操作。

這種方法稱為重復帶入法，或者迭代法。一般分為以下步驟：

1. 逐步展開遞歸式，一直到我們發(fā)現(xiàn)其中的模式為止。

2. 將該模式表示出來（通常會涉及一個求和式）并用變量i來表示其行號。

3. 根據(jù)i層遞歸將會達到基本情況來選擇i的值（并解決該求和式）。

 A Few Important Examples

　　遞歸式的一般形式：  T(n) = a · T(g(n)) + f(n)，a指遞歸調(diào)用的數(shù)量，g(n)遞歸過程所要解決的子問題大小，f(n)代表了函數(shù)中的額外操作。

遞歸式5：

　　T(n) =  T(n/2) + 1
               = { T(n/4) + 1 } + 1
               = { T(n/8) + 1 } + 1 + 1

　　令i=lgn ，得到 T(n) = Θ(lgn)

遞歸式6：

　　if k is a height, then n/2k is the number of nodes at that height . T(n) = Θ(n)

遞歸式8：

　　遞歸樹根節(jié)點上操作時間為n，后面的兩次遞歸調(diào)用中，各自執(zhí)行的都是減半操作，各節(jié)點的操作時間等于標簽值。

　　每一行的和為n，并且有l(wèi)gn+1行節(jié)點，得出總和為nlgn+n，Θ(nlgn)。

The Master Theorem  主定理

　　遞歸式與分治法存在的一般關系式為：　　T(n) = aT(n/b) + f(n) 

　　主要思想為：有a重調(diào)用，每重調(diào)用處理掉一定比例的數(shù)據(jù)（數(shù)據(jù)集的1/b），還存在一個額外的f(n)操作。   

三種基本情況：

1. 大部分操作都是運行在根節(jié)點上

2. 大部分操作運行在葉節(jié)點上

3. 均勻分布在該遞歸樹的各行之間

①、大部分操作都是運行在根節(jié)點上，總運行時間為Θ(f(n))

　　意味著：f(n)增長趨勢將嚴格快于葉節(jié)點數(shù)的增長。

　　T(n) = Θ(f(n)) = Θ(n)，如果看到b大于a，就立即可以確定n屬于表達式的主導部分

②、大部分操作運行在葉節(jié)點上

　　例如：T(n) = 2T(n/2)+ lgn ，葉子節(jié)點數(shù)為n，f(n)=lgn，運行時間就是計算葉節(jié)點數(shù)的時間 Θ(n)。

③、均勻分布在該遞歸樹的各行之間

　　求該樹各層操作之和的求和式

Merge Sort,  歸并排序例子：

The input (seq) has a size of n. There are two recursive calls, each on a subproblem of n/2

In addition, there is some work performed in a while loop and in res.reverse();  this work is Θ(n).

This gives us the well-known recurrence number 8, T(n) = 2T(n/2) + Θ(n), which means that the running time of merge sort is Θ(n lg n),  

Summer

The sum of the n first integers is quadratic, and the sum of the lg n first powers of two is linear.

The first of these identities can be illustrated as a round-robin tournament, with all possible pairings of n elements; 

the second is related to a knockout tournament, with lg n rounds, where all but the winner must be knocked out.  

A function is recursive if it calls itself (directly or via other functions). 

A recurrence relation is an equation that relates a function to itself, in a recursive way (such as T(n) = T(n/2) + 1).

These equations are often used to describe the running times of recursive algorithms, and to be able to solve them, we need to assume something about the base case of the recursion;