计算机科学领域的任何人都知道，理论上 HeapSort 是O(n log n)最坏的情况，而 QuickSort 是O(n^2)最坏的情况。然而，在实践中，一个良好实现的 QuickSort（具有良好的启发式）在每个数据集上都将优于 HeapSort。一方面，我们几乎没有观察到最坏的情况，另一方面，例如 CPU 缓存线、预取等在许多简单任务中产生了巨大的差异。虽然 QuickSort 可以处理 中的预排序数据（具有良好的启发式）O(n)，但 HeapSort 将始终重新组织 中的数据O(n log n)，因为它不利用现有结构。
对于我的玩具项目caliper-analyze，我最近一直在研究从基准测试结果中估计算法实际平均复杂度的方法。特别是，我尝试了 Lawson 和 Hanson 的 NNLS 拟合不同的多项式。
但是，它还不能很好地工作。有时我得到可用的结果，有时我没有。我认为进行更大的基准测试可能会有所帮助，尤其是尝试更多参数。
以下结果用于以 10% 随机性的 SAW 模式对 Double 对象进行排序。本次运行的 n 最高只有 500，因此对于实际使用来说不是很有代表性……这些数字是估计的运行时依赖于大小。输出是手工编辑和手动排序的，所以它不反映该工具当前提供的内容！
BubbleSortTextbook LINEAR: 67.59 NLOG2N: 1.89 QUADRATIC: 2.51
BubbleSort LINEAR: 54.84 QUADRATIC: 1.68
BidirectionalBubbleSort LINEAR: 52.20 QUADRATIC: 1.36
InsertionSort LINEAR: 17.13 NLOG2N: 2.97 QUADRATIC: 0.86
QuickSortTextbook NLOG2N: 18.15
QuickSortBo3 LINEAR: 59.74 QUADRATIC: 0.12
Java LINEAR: 6.81 NLOG2N: 12.33
DualPivotQuickSortBo5 NLOG2N: 11.28
QuickSortBo5 LINEAR: 3.35 NLOG2N: 9.67
您可以看出，虽然在这种特定设置下（通常它根本无法令人满意），但结果在很大程度上与已知行为一致：冒泡排序确实成本高昂，而快速排序的良好启发式方法要好得多。但是，例如，具有三个启发式中值的 QuickSort 最终会得到一个O(n + n^2)估计，例如，而其他 QuickSort 被估计为O(n + n log n)
所以现在我的实际问题：
- 您是否知道从基准数据执行运行时复杂性分析的算法/方法/工具，以预测哪种实现（如您在上面看到的，我有兴趣比较同一算法的不同实现！）在真实数据上表现最佳？
- 你知道这方面的科学文章吗（估计实现的平均复杂度）？
- 您知道有助于在这里获得更准确估计的稳健拟合方法吗？例如，NNLS 的正则化版本。
- 您是否知道需要多少样本才能获得合理估计的经验法则？（特别是，该工具何时应避免给出任何估计，因为它可能无论如何都不准确？）
让我再次强调，我对理论复杂性或形式分析不感兴趣。我有兴趣了解实现（理论上甚至是相同的算法）如何在真实 CPU 上的基准数据上执行......共同范围的数值因子对我来说是关键，而不是渐近行为。（不，从长远来看，这不仅仅是时间复杂度和排序。但我对索引结构和其他参数感兴趣。如果我没记错的话，caliper 也可以测量内存消耗）另外，我在java中工作。一种只调用 Matlab 内置函数的方法对我没有用，因为我并不生活在 matlab 世界中。
如果我有时间，我会尝试重新运行其中一些规模更大的基准测试，以便获得更多数据点。也许它会起作用......但我相信我可以使用更强大的回归方法来获得更好的估计，即使是从较小的数据集。另外，我想检测样本何时太小而无法进行任何预测！