分析归并排序算法的时间复杂度，可以根据算法的逻辑，分析每一个步骤的最坏情况，然后得到总体的时间复杂度；也可以利用数学中的『归纳假设法』，用几乎纯数学的方式来得到它的时间复杂度。而后者比前者好理解得多，所以，我认为要推导归并排序的时间复杂度的话，归纳假设的方法是不二之选。
『1』时间复杂度递推公式
将待排序的数组记为a。假设这里是用递归的方式实现的归并排序（易于理解）。
归并排序将a分为两半，分别排序，再把排序后的这两半归并为一个数组。对这两半，还是用归并排序的方法，把它们分别再分成两半来排序、归并。这样一直拆分下去，直到最后拆成的“两半”已经是两个单独的元素，就算是“到头”了（没得拆了）。
因此，在每一次递归的过程中，需要做两个递归调用（分别排序拆成的那“两半”数组），以及一个归并操作。
文章来源：http://www.codelast.com/
归并操作的时间复杂度是 
，而两个递归调用的时间复杂度是多少呢？
这里先假设一次递归调用的过程所耗费的时间是 
，则在问题的规模减半后（数组拆成了两半，所以规模减半了），递归调用耗费的时间就是 
了。
因此，归并排序耗费的时间的递推公式就是：
根据这个式子，我们如何用归纳假设法，求出归并排序的时间复杂度？
文章来源：http://www.codelast.com/
『2』归纳
归纳就是总结出归并排序的时间复杂度公式，说白了根据几个已知的计算结果来猜。
根据前面的递推公式，我们可以计算出：
计算到这里，规律已经非常明显了：
我们知道，在描述算法复杂度的时候，对数的底数无关紧要，通常省略它，因此这里我们就记为：
所以我们就归纳（也就是猜测）出了归并排序的时间复杂度。
文章来源：http://www.codelast.com/
『3』假设 ＆ 证明
假设什么呢？
我们当然是要假设上面归纳出的时间复杂度公式是正确的。在这样的假设下，来看看可以怎样证明归并排序的时间复杂度确实是
。由算法效率的定义，若一个算法的时间复杂度为
，则存在正常数 
和 
，使得 
对所有 
成立。那么，由上面的假设，可得：![t(n) = 2t\left( {\frac{n}{2}} \right) + n \le c \cdot \left[ {\frac{n}{2}\log \left( {\frac{n}{2}} \right)} \right] + n](https://www.codelast.com/wp-content/plugins/latex/cache/tex_996b100e709f1e52518379bf8952497b.gif)
在这里，我们根据假设的正确的时间复杂度公式，用算法效率的定义，得到了上面的不等式，我们下面要做的，就是继续推导这个不等式，使之满足：
，那么根据算法效率的定义，就可知归并排序算法的时间复杂度确实是 了。文章来源：http://www.codelast.com/
看推导：
![\begin{array}{l}t(n) = 2t\left( {\frac{n}{2}} \right) + n \le c \cdot \left[ {\frac{n}{2}\log \left( {\frac{n}{2}} \right)} \right] + n \le cn\log \left( {\frac{n}{2}} \right) + n\\ = cn(\log n - \log 2) + n = cn\log n - cn + n = cn\log n + (1 - c)n\end{array}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_521e5bc1d53ac7e219b73396afadf3a7.gif)
此时，我们只要取
，便可使得上面的式子 
，即： 
所以到这里，我们就成功地利用假设，证明了归并排序的时间复杂度确实是
。
文章来源：https://www.codelast.com/
➤➤ 版权声明 ➤➤
转载需注明出处：codelast.com
感谢关注我的微信公众号（微信扫一扫）：
