《算法导论（原书第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的实际效率。

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
算法步骤：


申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；


设定两个指针，最初位置分别为两个已经排序序列的起始位置；


比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；


重复步骤 3 直到某一指针达到序列尾；


将另一序列剩下的所有元素直接复制到合并序列尾。、



Python代码示例：

def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0));
return result