java - 估计实现的实际(非理论)运行时复杂性

Question

计算机科学的任何人都知道 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。

但是，它还不太好用。有时我会得到有用的结果，有时我不会。我认为做更大的基准测试可能会有所帮助，尤其是尝试更多参数。

以下结果用于对 Double 对象进行排序，采用具有 10% 随机性的 SAW 模式。这次运行的 n 最多只有 500，因此对于实际使用来说并不是很有代表性……这些数字是估计的运行时对大小的依赖性。输出是手动编辑和手动排序，因此它不反射(reflect)工具当前提供的内容!

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 上对基准数据执行...我对常见范围的数值因素很感兴趣，更多比渐近行为。 (不，从长远来看，这不仅仅是时间复杂度和排序。但我对索引结构和其他参数感兴趣。卡尺还可以测量内存消耗，如果我没记错的话)另外，我是在 java 中工作。仅调用 Matlab 内置函数的方法对我没有用，因为我不生活在 matlab 世界中。

如果我有时间，我会尝试使用更多的尺寸重新运行其中一些基准测试，以便获得更多的数据点。也许它会起作用......但我相信有更强大的回归方法可以用来获得更好的估计，即使是从较小的数据集中。另外，我想检测样本何时太小而根本无法进行任何预测!

Answer 1

如果你想要实际的复杂性，你最好测量它。在没有测量的情况下试图猜测程序将如何执行是非常不可靠的。

同一个程序在不同机器上的表现可能大相径庭。例如一种算法在一台机器上可能更快，但在另一台机器上可能更慢。

您的程序可能会变慢，具体取决于机器正在做什么，因此看起来不错但大量使用缓存等资源的算法可能会变慢，并且在必须共享这些资源时会使其他程序变慢。

在机器上单独测试算法比尝试在真实程序中使用它快 2-5 倍。

Do you know rules-of-thumb of how many samples one needs to get a reasonable estimate? (in particular, when should the tool refrain from giving any estimate, as it will likely be inaccurate anyway?)

要确定像 90% 或 99% 这样的百分位数，您需要 1/(1-p)^2，即对于 99% 的分位数，您在预热后至少需要 10,000 个样本。对于 99.9% 的瓷砖，您需要一百万。