《算法导论（原书第3版)》 ──   Introduction to Algorithms, third edition

主定理
规模为n的问题通过分治，得到a个规模为n/b的问题，每次递归带来的额外计算为c(n^d)

T(n) <= aT(n/b)+c(n^d)

那么就可以得到问题的复杂度为：

T(n) = O(n^d log(n)), if a = b^d
T(n) = O(n^d ), if a < b^d
T(n) = O(n^logb(a))), if a > b^d

证明方法
本来使用主定理是可以免去画递归树的，但为了证明主定理，还是需要画树。

可见，每次递归把问题分为a个规模为n/b的子问题。从根节点开始，共有logb(n)+1层，叶子节点数为a^(logb(n))。那么，第j层共有a^j个子问题，每个问题规模为n/b^j，每个子问题运算量为c*(n/b^j)^d需要完成的计算量为：

求和得到整个问题的运算量：

那么，根据a与b^d的关系，很容易得到主定理。

时间复杂度：需要多少时间
空间复杂度：需要多少内存空间
时间复杂度相关公式：
N*1个操作 = O(N)
O(N) + O(N) = O(N)
N/2 *1个操作 = 1/2 * O(N) = O(N)
O (N ^ 2) + O (N) = O (N ^ 2)
1+2+3....+N = N * (N + 1) / 2 = N * N / 2 + N / 2 = 1 / 2 * O (N ^ 2) + 1 / 2 * O (N) = O (N ^ 2) + O (N) = O (N ^ 2)
空间复杂度相关公式：
2个单位的内存空间 = O(1)
定理：if x的时间复杂度要由于y的时间复杂度，那么，假设存在一个足够大的数M，当n>M时，我们可以保证X的时间效率要优于Y的实际效率。