algorithm - 什么时候简单排序比 'complex' 排序快？

Question

学校给我布置了一项排序算法作业，我们的任务是复习几种排序算法。报告的其中一个部分是关于“什么时候简单排序更快”。

我的排序算法是:

• 冒泡排序
• 选择排序
• 插入

都是 O(n^2) 的平均值

然后我有以下 O(n log n) 算法:

• 合并排序
• 快速排序

和基数排序 O(kn)

我对未排序和排序的数据进行了多次测试，范围从 10 到 100,000 的 n 个条目，并且复杂排序 O(n log n) 的执行速度总是更快。

我还尝试使用包含 n 个元素的排序数据集，其中 n = 10 到 n = 100,000

但 O(n log n) 算法仍然更快。

所以我的问题是，什么时候简单排序比复杂排序快。

谢谢， 克里斯。

Answer 1

运行时间与输入大小的平方成正比的排序的内部循环内的分支往往非常简单。

在这方面，插入排序通常效果最好。

另一方面，对于大小为 N 的输入，运行时间与 N log N 成正比的排序具有更复杂的分支。

分支复杂性在运行时显示为一个常量因素。所以我们有简单和复杂的运行时间

S N^2  and  C N log N

在较旧的计算机上，S 往往比 C 小很多。假设 S = 1 和 C = 4 只是为了好玩，那么你有一个可以求解的方程:

1 N^2 = 4 N log N

感兴趣的解是 N = 16(对数以 2 为底)。这是输入的大小，其中“简单”算法具有的更好速度的常数因子被更好的渐近速度所克服。小于 16 的输入将被 simple 算法更快地排序!当 N > 16 时，复杂算法的威力“开始”。

但是，在现代计算机中 - 正如您所发现的那样 - 在硬件级别更快的分支和更好的编译器使 S 和 C 更加接近。根据我的经验，关于 N^2 排序运行得更快的古老民间传说仅适用于微型嵌入式处理器。