如何测试完美优化的算法?

对于我们这些凡人来说,他们只想知道一个算法:

• 按预期合理工作;
• 比别人快;

有一个简单的步骤叫做“基准测试”。

挑选该地区最好的竞争者,并与你的算法进行比较。

如果您的算法获胜,那么它将更好地满足您的需求(由

没有简单的方法证明任何给定的算法是渐近最优的。

证明最优性(如果有的话)有时会在算法编写之后的几年和/或几十年。一个典型的例子是 Union-Find/disjoint-set data structure .

不相交的集合林是一种数据结构,其中每个集合由树数据结构表示,其中每个节点持有对其父节点的引用。它们最初是由伯纳德A。盖勒和迈克尔J。费舍尔在1964年,虽然他们的精确分析花了数年时间。

[…]这两种技术相辅相成;综合起来计算,每个工序的摊销时间仅为 O(α(n)) ,在哪里 α(n) 是函数的逆函数 f(n) = A(n,n) A 是不是增长非常快 Ackermann 功能。

对于某些算法来说,最优性可以通过非常仔细的分析来证明,但一般来说,一旦一个算法被编写出来,就很难判断它是否是最优的。事实上,要证明算法是否正确并不总是容易的。

另请参见

• Wikipedia/Matrix multiplication
  • 天真的算法是 O(N 3 ) , Strassen's O(无) 2.807 ) , Coppersmith-Winograd 是 O(无) 2.376 )
• Wikipedia/Asymptotically optimal

  目前许多最著名的算法是否是渐近最优的是一个开放的问题。例如,有一个 O(nα(n)) 求最小生成树的算法。这个算法是否渐近最优还不得而知,如果用任何一种方法来解决这个问题,都有可能成为一个重要的结果。

实际考虑

请注意,由于许多因素(例如,易于实现、给定输入参数范围的实际性能更好等),有时渐近“更差”算法在实践中更好。

一个典型的例子是 quicksort 简单的枢轴选择可能表现出二次最坏情况的性能,但在许多情况下仍优于更复杂的变量和/或其他渐近最优排序算法。