分治的前提
1. 一个大的问题可以分割为n个小的问题， 并且小问题的解决方式与大问题的一致
2. 问题可以分割
3. 解决结果可以合并
分治算法的典型分类
================Decreasing=================
1. T(n) = T(n-1)+1 O(n)
2. T(n) = T(n-1) + n O(n^2)
3. T(n) = T(n-1) + logn O(nlogn)
4. T(n) = 2T(n-1) +1 O(2^n)
5. T(n) = 2T(n-1) + n O(n2^n)
================Dividing======================
6. T(n) = T(n/2) +1 O(logn)
7. T(n) = T(n/2) +n O(n)
8. T(n) = 2T(n/2) +n O(nlogn)
================Root=========================
9. T(n) = T(n½) +1 O(loglogn)
