关于归并排序时间复杂度 T（n） =2T（n/2）+O（n）

本文主要是介绍关于归并排序时间复杂度 T（n） =2T（n/2）+O（n），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

T（n）=2T（n/2）+O（n），n=2^k。
想知道为什么最终答案为O（nlgn）

---

Master大法好。这题自己推导也不难。把递推公式重复代入三次并化简：

 

可以看出规律了，而且很容易用归纳法证明。于是代入k次时就有（n=2k）：

https://segmentfault.com/q/1010000008698385

 

 

这篇关于关于归并排序时间复杂度 T（n） =2T（n/2）+O（n）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---