algorithm - 为什么首选增长顺序作为运行时算法性能的基准？

Question

我了解到增长率通常用于衡量算法的运行时间和效率。我的问题是为什么使用增长率而不是使用运行时和输入大小之间的精确(或近似)关系？

编辑:

感谢您的回复。我想澄清一下“运行时和输入大小之间的关系”是什么意思，因为它有点含糊。

据我了解，增长率是运行时相对于输入的梯度。因此，n^2 的增长率将给出 t = k(n^3) + Constant 形式的方程。考虑到方程式的信息量更大(因为它包含常数)并且显示与所需时间的直接关系，我认为它会是首选。

我确实明白，随着 n 的增加，常数很快就会变得无关紧要，并且根据不同的计算配置，k 会有所不同。也许这就是为什么仅使用增长率就足够了。

Answer 1

算法并不是影响实际运行时间的唯一因素

编程语言、优化、分支预测、I/O 速度、分页、处理速度等因素都会发挥作用。

一种语言/机器/任何东西肯定比另一种有优势，因此每种算法都需要在完全相同的条件下执行。

除此之外，当考虑驻留在 RAM 中的输入和输出时，一种算法可能优于 C 语言中的另一种算法，但当考虑驻留在磁盘中的输入和输出时，另一种算法可能优于 Python 中的第一种算法。

毫无疑问，几乎没有机会就应该用于执行所有基准测试的确切条件达成一致，而且，即使可以达成这样的一致，使用 5 岁的 child 肯定是不负责任的当今计算世界的基准测试结果，因此需要定期为所有算法重新创建这些结果 - 这将是一项庞大且非常耗时的任务。

算法有不同的常数因子

在极端情况下，某些算法的常数因子非常高，以至于现代其他渐近较慢的算法在所有合理输入上都优于它。如果我们只看运行时间，那么这些算法在较大输入上优于其他算法的事实可能会丢失。

在不太极端的情况下，由于涉及的常数因素，我们会得到与其他输入大小不同的结果 - 我们可能会看到一种算法在我们所有的测试中都更快，但一旦我们达到某个输入大小，另一个可能会变得更快。

一些算法的运行时间在很大程度上取决于输入

例如，对已排序数据的基本快速排序需要 O(n^2)，而平均需要 O(n log n)。

当然可以确定最好和最坏的情况并针对这些情况运行算法，但平均情况只能通过数学分析来确定 - 你不能为“平均情况”运行它 - 你 可以针对随机输入运行它很多次并得到平均值，但这相当不精确。

所以粗略估计就足够了

由于上述原因，仅说一个算法是有意义的，例如，O(n^2)，这非常粗略地意味着，如果我们处理足够大的输入大小，则需要 4如果输入大小加倍，则时间更长。如果您一直在关注，您就会知道实际花费的时间可能与 4 倍长的时间有很大不同，但它至少给了我们一些想法 - 我们预计不会花费两倍长，也不是 10 倍长(尽管在极端情况下可能会如此)。我们也可以合理地期望，例如，对于大 n，O(n log n) 算法优于 O(n^2) 算法，这是一个有用的比较，并且可能比某些人更容易看到发生了什么更准确的表示。