关于归并排序运行时间的证明

《算法导论》第三版第二章利用了插入排序和归并排序学习了关于程序的运行时间！

我利用课后证明题来演示，如何利用数学归纳法证明归并排序的程序运行时间！

关于归并排序的实现，我已经在上一篇文章提供了一个几乎完美的代码，需要的同学可以去借鉴一下吧！

原题如下：

使用数学归纳法证明：当n刚好是2的幂时，以下递归式的解是T（n）= nlgn。

当n = 2 时， T（n）= 2；

当n = 2^k,k>1时，T(n) = 2T(n/2) + 2 。

这是数学了典型的分段函数，还有一个要说明的是，^代表幂，*代表乘号、这里的lgn 不是中学数学里常说的以10为底n的对数，而是以2为底n的对数。

证明：

（1）	当n = 2时：
			T(2) = 2 * lg2 = 2， 显然接成立；
（2）	当n = 2^k，且k>1时：
			由已知，T(n) = 2 * T(n/2) + n ，当n = 2^k，且k>1时的解为T(n) = n * lgn；
（3）	当n = 2^(k+1)时：
			T(n) = 2 * T(n/2) + n = 2 * T(2^k) + 2^(k+1)
				 = 2 * 2^k * lg(2^k) + 2^(k+1)
				 = 2^(k+1) * (k + 1)
				 = 2^(k+1) * lg(2^(k+1))

所以，当n = 2^(k+1)时，结论也成立。
综上所述，当n刚好是2的幂时，
式子：
当n = 2 时， 		T（n）= 2；
当n = 2^k,k>1时，T(n) = 2T(n/2) + 2 
的解为 ：T（n）= nlgn。

我已经尽量用标准的方法描述了整个证明过程，其实很简单的！习惯数学归纳法的方法证明这一类题就比较简单了！

关于归并排序运行时间的证明,布布扣,bubuko.com

关于归并排序运行时间的证明

原文：http://blog.csdn.net/tiny39st/article/details/21562563