【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

这三种方法分别是：代入法，递归树法，和主方法。代入法是一种十分强大的方法，它几乎可以求解所有的递归式。然而，对于一些“小鸡”来说，不需要这么强大的“牛刀”。对于一些特定类型的递归式（具体类型在主方法的小节中会介绍），用主方法可以用更少的时间得到一个更确切的界。