没有简单的方法可以证明任何给定的算法都是渐近最优的.
证明最优性(如果有的话)有时在算法写入之后的几年和/或几十年之后.一个典型的例子是Union-Find/disjoint-set数据结构.
脱节集林是一种数据结构,其中每个集由树数据结构表示,其中每个节点都拥有对其父节点的引用.它们首先由Bernard A. Galler和Michael J. Fischer于1964年描述,尽管他们的精确分析需要数年时间.
[...]这两种技术相互补充; 一起应用,每个操作的摊销时间仅为
O(?(n)),?(n)函数的倒数在哪里f(n) = A(n,n),并且A是非常快速增长的Ackermann函数.[...]事实上,这是渐近最优的:Fredman和Saks在1989年表明,每个操作平均必须通过任何不相交的数据结构访问Ω(α(n))个字.
对于某些算法,经过非常仔细的分析可以证明最优性,但一般来说,一旦算法编写完成,就没有简单的方法可以判断算法是否是最优的.实际上,要证明算法是否正确并不总是很容易.
O(N3)O(N2.807)O(N2.376)今天许多最着名的算法是否渐近最优是一个悬而未决的问题.例如,存在
O(n?(n))用于查找最小生成树的算法.该算法是否渐近最优是未知的,并且如果以任一方式解决,则可能被称为重要结果.
请注意,由于许多因素(例如,易于实现,实际上对于给定输入参数范围实际上更好的性能等),有时渐近"更差"的算法在实践中更好.
典型的例子是具有简单枢轴选择的快速排序,其可以表现出二次最坏情况性能,但是在许多情况下仍然优于更复杂的变体和/或其他渐近最优排序算法.