【Algorithm】Divide And Conquer & Complexity calculation
1、Divide the problem into a number of subproblems that are smaller instances of the same problem.
2、Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
- 3、Combine the solutions to the subproblems into the solution for the original problem.
归并排序就是一个用分治法的经典例子，这里我用它来举例描述一下上面的步骤：
1、归并排序首先把原问题拆分成2个规模更小的子问题。
2、递归地求解子问题，当子问题规模足够小时，可以一下子解决它。在这个例子中就是，当数组中的元素只有1个时，自然就有序了。
3、最后，把子问题的解（已排好序的子数组）合并成原问题的解。
Recursion Expression
利用递归式分析分治法复杂度 : 1.写出递归式 （递归+分解复杂度+合并复杂度） 2.画出递归树 3.计算
Ways to calc Recursion Expression
这三种方法分别是：代入法，递归树法，和主方法。代入法是一种十分强大的方法，它几乎可以求解所有的递归式。然而，对于一些“小鸡”来说，不需要这么强大的“牛刀”。对于一些特定类型的递归式（具体类型在主方法的小节中会介绍），用主方法可以用更少的时间得到一个更确切的界。
