3

我想得到理论原因而不是实验结果。另外，我们如何确定数据大小何时称为小或大？

我没有解释清楚，我的意思是当输入数据量较小时，我们通常选择使用插入排序或不使用快速排序，没错。所以我想知道这是为什么？

4

1 回答 1

16

请记住，在渐近分析中，我们忽略了常数因素。所以 Quicksort 的 O(n log n) 复杂度实际上是 O(C(n log n))，其中 C 是某个未知常数。同样，插入排序的 O(n^2) 实际上是 O(C(n^2))。我们称这些常数为 Cq 和 Ci。

因此，当 (Ci * n^2) < (Cq * (n log n)) 时，插入排序会更快。

看一下 Ci < Cq 的两种算法应该很明显。插入排序非常简单。该算法只不过是比较和交换，并带有一点循环开销。

快速排序稍微复杂一点，每次迭代需要更多步骤，但迭代次数更少。

考虑对一个五元素数组进行排序。插入排序会做，最坏的情况是：

  • 5 外环控制变量的增量和比较
  • 内循环控制变量的 15 个增量和比较
  • 15个元素比较
  • 15 次互换

现在看看Quicksort，它在平均情况下必须划分四个子数组。5 个元素的数组被分成 3 个和 2 个元素的两个子数组。3 元素子阵列进一步划分为 1 和 2 元素的子阵列。然后对两个 2 元素子数组进行分区。

因此该partition方法将被调用四次。除了元素的比较和交换以及其他开销之外，每个分区步骤至少需要两次交换。当您将所有内容加起来时，您会发现 Quicksort 每次迭代都做了更多的工作。当迭代次数较少时，即使迭代次数较多，插入排序的总工作量也会较少。

您可以进行逐步分析以确定“小”的理论值，其中插入排序将比快速排序更快。通常这是通过计算“基本操作”来完成的，尽管定义有些灵活。在这种情况下，这很容易：比较、赋值或函数调用是“基本操作”。

理论结果与实验得出的结果如何匹配将取决于特定的计算机硬件以及比较的成本。如果比较非常昂贵，那么您将需要选择执行最少比较次数的算法。但是，如果比较相对便宜（例如，比较数字，甚至是字符串，只要它们没有长的公共前缀），那么算法开销就是限制因素，简单低效算法优于复杂高效算法。

于 2013-10-28T16:12:05.953 回答