algorithm - 如何测试完美优化的算法？

Question

有什么方法可以测试算法是否完美优化？

Answer 1

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

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

Disjoint-set forests are a data structure where each set is represented by a tree data structure, in which each node holds a reference to its parent node. They were first described by Bernard A. Galler and Michael J. Fischer in 1964, although their precise analysis took years.

[...] These two techniques complement each other; applied together, the amortized time per operation is only O(α(n)), where α(n) is the inverse of the function f(n) = A(n,n), and A is the extremely quickly-growing Ackermann function.

[...] In fact, this is asymptotically optimal: Fredman and Saks showed in 1989 that Ω(α(n)) words must be accessed by any disjoint-set data structure per operation on average.

对于某些算法，可以在非常仔细的分析后证明其最优性，但一般来说，一旦算法编写完成，就没有简单的方法来判断它是否最优。事实上，证明算法是否正确并不总是那么容易。

另见

• Wikipedia/Matrix multiplication
  • 朴素算法是O(N3), Strassen's大致是 O(N2.807)，Coppersmith-Winograd是 O(N2.376)，我们仍然不知道什么是最优的。
• Wikipedia/Asymptotically optimal

  it is an open problem whether many of the most well-known algorithms today are asymptotically optimal or not. For example, there is an O(nα(n)) algorithm for finding minimum spanning trees. Whether this algorithm is asymptotically optimal is unknown, and would be likely to be hailed as a significant result if it were resolved either way.

---

实际考虑

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

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