转载请注明出处:http://www.codelast.com/

分析归并排序算法的时间复杂度,可以根据算法的逻辑,分析每一个步骤的最坏情况,然后得到总体的时间复杂度;也可以利用数学中的『归纳假设法』,用几乎纯数学的方式来得到它的时间复杂度。而后者比前者好理解得多,所以,我认为要推导归并排序的时间复杂度的话,归纳假设的方法是不二之选。

『1』时间复杂度递推公式
将待排序的数组记为a。假设这里是用递归的方式实现的归并排序(易于理解)。
归并排序将a分为两半,分别排序,再把排序后的这两半归并为一个数组。对这两半,还是用归并排序的方法,把它们分别再分成两半来排序、归并。这样一直拆分下去,直到最后拆成的“两半”已经是两个单独的元素,就算是“到头”了(没得拆了)。
因此,在每一次递归的过程中,需要做两个递归调用(分别排序拆成的那“两半”数组),以及一个归并操作。
文章来源:http://www.codelast.com/
归并操作的时间复杂度是 O\left( n \right) ,而两个递归调用的时间复杂度是多少呢?
这里先假设一次递归调用的过程所耗费的时间是 t(n) ,则在问题的规模减半后(数组拆成了两半,所以规模减半了),递归调用耗费的时间就是 t\left( {\frac{n}{2}} \right) 了。
因此,归并排序耗费的时间的递推公式就是:
t(n) = t\left( {\frac{n}{2}} \right) + t\left( {\frac{n}{2}} \right) + n = 2t\left( {\frac{n}{2}} \right) + n,\;n > 1
根据这个式子,我们如何用归纳假设法,求出归并排序的时间复杂度?
文章来源:http://www.codelast.com/
『2』归纳
归纳就是总结出归并排序的时间复杂度公式,说白了根据几个已知的计算结果来猜。
根据前面的递推公式,我们可以计算出:

t(2) = 2t(1) + 2 = 2 = 2 \cdot {\log _2}2
t(4) = 2t(2) + 4 = 8 = 4 \cdot {\log _2}4
t(8) = 2t(4) + 8 = 24 = 8 \cdot {\log _2}8
计算到这里,规律已经非常明显了: t(n) = n{\log _2}n
我们知道,在描述算法复杂度的时候,对数的底数无关紧要,通常省略它,因此这里我们就记为: t(n) = n\log n
所以我们就归纳(也就是猜测)出了归并排序的时间复杂度。
文章来源:http://www.codelast.com/
『3』假设 & 证明
假设什么呢?
我们当然是要假设上面归纳出的时间复杂度公式是正确的。在这样的假设下,来看看可以怎样证明归并排序的时间复杂度确实是 O\left( {n\log n} \right)
由算法效率的定义,若一个算法的时间复杂度为 O\left( {n\log n} \right) ,则存在正常数 cN ,使得 f(n) \le c\left( {n\log n} \right) 对所有 n \ge N 成立。那么,由上面的假设,可得:
t(n) = 2t\left( {\frac{n}{2}} \right) + n \le c \cdot \left[ {\frac{n}{2}\log \left( {\frac{n}{2}} \right)} \right] + n
在这里,我们根据假设的正确的时间复杂度公式,用算法效率的定义,得到了上面的不等式,我们下面要做的,就是继续推导这个不等式,使之满足: t(n) \le c\cdot\left( {n\log n} \right) ,那么根据算法效率的定义,就可知归并排序算法的时间复杂度确实是 O\left( {n\log n} \right) 了。
文章来源: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}
此时,我们只要取 c \ge 1 ,便可使得上面的式子  \le cn\log n ,即: t(n) \le c \cdot \left( {n\log n} \right)
所以到这里,我们就成功地利用假设,证明了归并排序的时间复杂度确实是 O\left( {n\log n} \right)
[原创] 如何用「归纳假设法」求归并排序的时间复杂度
Tagged on:                 

发表评论

电子邮件地址不会被公开。 必填项已用*标注