算法算法分析

在归并排序中对小数组采用插入排序

字数统计: 1.1k字   |   阅读时长: 3分
,

摘要: 使递归的叶子变粗

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 分治算法的设计与分析-归并排序 中，我们了解了分治算法的设计和分析方法，并且得出了归并排序算法的最坏情况运行时间为 $\Theta(n\log n)$。

在文章 基于随机访问机模型分析算法 中，我们了解了算法分析的方法论，并且以插入排序为例，得到了插入排序最坏情况运行时间为 $\Theta(n^{2})$。

虽然看起来好像归并排序比插入排序的运行时间要好，但插入排序中的常量因子可能使得它在 n 较小时，在许多机器上实际运行得更快。因此归并排序中，当子问题规模足够小时，采用插入排序使得递归的叶变粗是有意义的。

那么一个自然的问题就是：在归并排序的分解-解决-合并的流程中，当分解后的子问题的规模多小的时候采用插入排序，可以取得收益。本文我们就来分析这个问题。

问题描述

考虑长度为 n 的数组，使用插入排序来排序长度为 $k$ 的 $\frac{n}{k}$ 个子表，然后用归并排序的合并机制来合并这些子表。

分析这个算法的运行时间，与归并排序进行对比，并研究实践中选择 k 的策略。

排序 $n/k$ 个子表的运行时间

插入排序一个长为 $k$ 的数组，最坏情况的运行时间为 $\Theta(k^{2})$，于是排序 $\frac{n}{k}$ 个子表的运行时间为：

合并 $n/k$ 个子表的运行时间

合并 $K$ 个已排序的数组(链表)，每个已排序数组长度为 $N$，合并后总长度为 $KN$。在 力扣23-合并K个升序链表 中我们解决过这个问题，有堆和分治两种方法，运行时间一样。分析过程如下：

如果用堆的方法，堆的容量为 $K$，因此堆的插入删除运行时间 $\Theta(\log K)$，而 $K$ 个已排序数组的总长度为 $KN$，因此总的运行时间为：$\Theta(KN\log K)$。

如果用分治法，过程如下：

  • 分解：将 $K$ 个已排序数组分为两份，每份 $K / 2$ 个
  • 解决：如果 $K = 1$，可以直接解决，运行时间 $\Theta(1)$
  • 合并：将两个有序数组合并为 1 个

按照以上流程，每一轮合并 $\frac{K}{2}$ 组链表，每一组 2 个，因此每组运行时间为 $\Theta(2N)$；每二轮合并 $\frac{k}{4}$ 组链表，每一组 4 个，因此每组运行时间为 $\Theta(4N)$，以此类推，总运行时间为 $\Theta(\sum\limits_{i=1}\limits^{\log K}\frac{K}{2^{i}}\times 2^{i}N) = \Theta(KN\log K)$。

这里我们是要合并 $\frac{n}{k}$ 个已排序数组，每个的长度为 $k$，合并后总长度 $n$，因此合并的运行时间为 $\Theta(n\log \frac{n}{k})$。

整体的运行时间

在归并排序中，对小数组用插入排序，分为排序 $n/k$ 个子表，合并 $n/k$ 个子表两步，前面分别分析了这两步的运行时间，因此总运行时间为：

可以看到，修改过的算法的运行时间最低也是 $\Theta(n\log n)$，与归并排序一样。如果 $k$ 取的不好，比如 $k > \log n$，修改过的算法的运行时间还会大于归并排序的 $\Theta(n\log n)$。

实践中如何选择 k

根据具体的计算环境，选择使得插入排序比归并排序快的最大的 $k$，但最大不要大于 $\log n$。

Share