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

Question

计算机科学领域的任何人都知道HeapSort O(n log n)在理论上是O(n^2)最糟糕的,而QuickSort是最糟糕的情况.但是,实际上,一个实现良好的QuickSort(具有良好的启发式)将在每个数据集上优于HeapSort.一方面,我们几乎没有观察到最坏的情况,另一方面,例如CPU缓存线,预取等在许多简单的任务中产生巨大的差异.虽然例如QuickSort可以处理预分类数据(具有良好的启发式)O(n),但HeapSort将始终重新组织数据O(n log n),因为它不利用现有结构.

对于我的玩具项目卡尺分析,我最近一直在研究从基准测试结果中估算算法的实际平均复杂度的方法.特别是,我尝试过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上的一个好的启发式方法要好得多.但是,例如,具有三个中值启发式的QuickSort最终会进行O(n + n^2)估算,而其他QuickSort估计为O(n + n log n)

那么现在我的实际问题:

• 您是否知道从基准数据执行运行时复杂性分析的算法/方法/工具,以便预测哪个实现(如您所见,我对比较同一算法的不同实现感兴趣!)在真实数据上表现最佳？
• 你知道关于这方面的科学文章(估计实现的平均复杂性)吗？
• 您是否知道有效的拟合方法有助于在此获得更准确的估算？例如NNLS的正则化版本.
• 您是否知道需要多少样本来获得合理估计的经验法则？(特别是,工具什么时候不应该给出任何估计,因为它可能是不准确的？)

让我再次强调,我对理论复杂性或形式分析不感兴趣.我有兴趣了解实际(在理论上甚至是相同的算法)的实现如何对真实CPU上的基准数据执行... 对于我来说,共同范围的数值因子比关键渐近行为更重要.(不,从长远来看,它不仅仅是时间复杂性和排序.但我对索引结构和其他参数感兴趣.如果我没有弄错的话,卡尺也可以测量内存消耗)另外,我是在java工作.一个只调用Matlab内置的方法对我来说毫无用处,因为我不是生活在matlab世界中.

如果我有时间,我将尝试重新运行一些具有更多种类的基准测试,因此我获得了更多的数据点.也许它会起作用......但我相信有更强大的回归方法可以用来获得更好的估算,即使是从较小的数据集.另外,我想检测样品何时太小而无法进行任何预测!

Answer 1

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

同一个程序在不同的机器上执行起来可能会有很大不同。例如，一种算法可能在一台机器上更快，但在另一台机器上更慢。

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

在机器上测试算法本身比在真实程序中使用算法快 2-5 倍。

您知道需要多少样本才能获得合理估计的经验法则吗？（特别是，该工具何时应该避免给出任何估计，因为无论如何它都可能不准确？）

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