我希望获得理论原因而非实验结果。此外，我们如何确定数据规模何时被称为小或大？
我没有解释清楚，我的意思是当输入数据规模较小时，我们通常选择使用插入排序而不是快速排序，这是正确的。那么我想知道原因是什么？
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。插入排序非常简单。该算法仅涉及比较和交换，还有一些循环开销。
Quicksort稍微复杂一些，需要每次迭代执行更多步骤，但迭代次数更少。
考虑对一个五元素数组进行排序。最坏情况下，插入排序将执行：
- 5次外部循环控制变量的递增和比较 - 15次内部循环控制变量的递增和比较 - 15次元素比较 - 15次交换
现在看一下快速排序, 平均情况下需要将四个子数组进行划分。5个元素的数组被分成了两个包含3个和2个元素的子数组。3个元素的子数组又被进一步划分为包含1个和2个元素的子数组。然后，这两个子数组也被划分。
所以，
您可以进行逐步分析，确定"小"的理论值，在此范围内，插入排序比快速排序更快。通常这是通过计算 "基本操作" 来完成的，尽管定义有些灵活。在这种情况下，它非常容易: 比较、赋值或函数调用都是 "基本操作"。
理论结果与实验结果的匹配程度将取决于特定的计算机硬件以及比较的成本。如果比较非常昂贵，那么您需要选择进行最少比较次数的算法。但是，如果比较相对便宜（例如比较数字或字符串，只要它们没有长的共同前缀），则算法开销是限制因素，简单低效的算法胜过复杂高效的算法。
因此，当(Ci * n^2) < (Cq * (n log n))时，插入排序将更快。
从两个算法的外观上看，显然Ci < Cq。插入排序非常简单。该算法仅涉及比较和交换，还有一些循环开销。
Quicksort稍微复杂一些，需要每次迭代执行更多步骤，但迭代次数更少。
考虑对一个五元素数组进行排序。最坏情况下，插入排序将执行：
- 5次外部循环控制变量的递增和比较 - 15次内部循环控制变量的递增和比较 - 15次元素比较 - 15次交换
现在看一下快速排序, 平均情况下需要将四个子数组进行划分。5个元素的数组被分成了两个包含3个和2个元素的子数组。3个元素的子数组又被进一步划分为包含1个和2个元素的子数组。然后，这两个子数组也被划分。
所以，
partition方法会被调用四次。每次划分步骤除了比较和交换元素以及其他开销外，还需要至少进行两次交换。当你把所有这些加起来，你会发现快速排序每次迭代要做更多的工作。当迭代次数很小的时候，尽管它做了更多的迭代，但插入排序总体上做的工作更少。您可以进行逐步分析，确定"小"的理论值，在此范围内，插入排序比快速排序更快。通常这是通过计算 "基本操作" 来完成的，尽管定义有些灵活。在这种情况下，它非常容易: 比较、赋值或函数调用都是 "基本操作"。
理论结果与实验结果的匹配程度将取决于特定的计算机硬件以及比较的成本。如果比较非常昂贵，那么您需要选择进行最少比较次数的算法。但是，如果比较相对便宜（例如比较数字或字符串，只要它们没有长的共同前缀），则算法开销是限制因素，简单低效的算法胜过复杂高效的算法。
- Jim Mischel
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接