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