讨厌算法的程序员 7 - 归并排序的时间复杂度分析

讨厌算法的程序员系列入口

递归树

上一篇归并排序基于分治思想通过递归的调用自身完成了排序，本篇是关于归并排序的最后一部分——分析其时间复杂度。

这个过程中会解释清楚在各种时间复杂度中经常看到的一个记号——“lgn”（以2为底的对数函数）是如何产生的。

递归式

代码分析

对归并排序代码进行逐行分析，当有n > 1个元素时，分解运行时间如下：

分解：第1行是判断，第2行是分解步骤（仅仅计算中间位置），都只需要常量时间，因此D₁(n) = Θ(1)，D₂(n) = Θ(1)。

解决：原问题分解成了2个子问题，每个子问题的规模是原问题的1/2。为了求解一个规模为n/2的子问题，第3行和第4行，各需要T(n/2)的时间，所以一共需要2T(n/2)的时间来求解2个子问题。

合并：在合并算法中已经知道在一个具有n个元素的数组上进行两个子数组MERGE需要Θ(n)的时间，即第5行C(n) = Θ(n)。

将每行的执行时间相加：

T(n) = 2T(n/2) + D₁(n) + D₂(n) + C(n) (当n > 1)

T(n)的表达式中又包含了T，所以上式称为T(n)的递归式。

根据分析进行简化可得到：

T(n) = 2T(n/2) + Θ(n) (当n > 1)

求解递归式

求解递归式，即得到描述T(n)与输入规模n关系的函数表达式的过程。为方便起见，假设n刚好是2的幂（子数组总可以被2整除直到只有1个元素为止）。该假设不影响递归式解的增长量级。

重写递归式为：T(n) = 2T(n/2) + cn (当n > 1)，然后手绘出“递归”层层展开的样子——递归树：

• 图(a)为T(n)，是未进行递归时的表达；
• 图(b)为扩展成一棵描绘递归式的等价树，cn是树根（代表递归的顶层算法中的代价），根的两棵子树是两个较小的递归式T(n/2);
• 图(c)是继续扩展T(n/2)后的样子。

构造递归树

如此层层递归扩展，得到一颗完整的递归树如下：

完整递归树

将递归式完全扩展后，形成了完整的递归树，一共是lgn+1层（如果n是8，则树有lg8+1=4层），每层的代价是cn，那么总代价cnlgn+cn，忽略低阶项和常量c，即有T(n) = Θ(nlgn)。

关于Θ(nlgn)

现在知道时间复杂度中的lgn是如何产生的了：是基于递归的原因。

lgn即log₂n，是以2为底的对数函数，比任何线性函数增长要慢，所以在足够大的输入情况下，在最坏情况下，运行时间为Θ(nlgn)的归并排序将优于运行时间为 Θ(n²)的插入排序。

y=x与y=lgx

上一篇 6 归并排序

---

共享协议：署名-非商业性使用-禁止演绎（CC BY-NC-ND 3.0 CN）
转载请注明：作者黑猿大叔（简书）