学习算法笔记（5）

学习过分治方法来设计归并排序算法之后，发现它的效率是大大地提升了，但是我们怎么样知道它效率是提升的呢？又需要使用什么样的方法来计算它的时间呢？这些问题会一个一个困扰着大家。要解决这些问题，需要分析归并排序算法的时间占用，看看它的耗时与数量n之间的关系。

       当一个算法包含对其自身的递归调用时，往往可以使用递归方程或递归式来描述其运行时间，然后通过数学工具来对时间进行计算。针对归并排序，下面详细地展开地分析它的时间计算。假定归并排序解决一个问题的时间为T（n），如果这个问题分解之后，足够小，那么时间就为T（1）。由于存在递归，那么就需要另外两部分时间：分解和合并。分解时间为D（n），合并时间为C（n），因此就可以把递归过程中每一步的时间写成下面的公式：

T（n） = T(1)  当n <= 1时。

T（n） = aT(n) + D(n) + C(n) ， 当n>1时。

这里可以看到D（n）和C（n）都n的线性函数，可以把它进一步合并，那么就可以写成这样：

T（n） =c  当n <= 1时