查看“︁渐进最优”︁的源代码

在[[计算机科学]]中，'''渐进最优'''一词用以评价算法的效率。如果已经证实一个问题需要使用[[大Ω符号|Ω(f(n))]]的资源来解决，而某个算法用[[大O记号|O(f(n))]]的资源来解决这个问题，则该算法就是渐进最优的。

渐进最优的例子包括[[数据结构]][[动态数组]]<ref>{{Citation
| title=Resizable Arrays in Optimal Time and Space
| url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf
| year=1999
| first1=Andrej
| last1=Brodnik
| first2=Svante
| last2=Carlsson
| first5=ED
| last5=Demaine
| first4=JI
| last4=Munro
| first3=Robert
| last3=Sedgewick
| author3-link=Robert Sedgewick (computer scientist)
| publisher=Department of Computer Science, University of Waterloo
| accessdate=2019-05-12
| archive-date=2020-10-29
| archive-url=https://web.archive.org/web/20201029091815/https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf
| dead-url=no
}}</ref>，能够在常数时间内索引，但性能在多数机器上不如普通数组的索引。另外，在所有基于比较的排序算法中，[[归并排序]]和[[堆排序]]是渐进最优的<ref>{{cite book |author1=Robert Sedgewick |author2=Kevin Wayne |title=Algorithms |publisher=Addison-Wesley |isbn=978-0-321-57351-3 |edition=4th}}</ref>{{rp|282, 326}}。

== 加速 ==
渐近最优算法的不存在性称为加速比。 布鲁姆加速定理表明存在人为构造的加速问题。 然而，目前许多最著名的算法是否是渐近最优的，这是一个公开的问题。 例如，有一种算法可以找到最小生成树，这是一个非常缓慢增长的阿克曼函数，但是最著名的下界是微不足道的。<math>O(n\alpha(n))</math><math>\alpha(n)</math><math>\Omega(n)</math> 这个算法是否是渐近最优的是未知的，如果它被解决了，可能会被欢呼为一个重要的结果。 Coppersmith 和 Winograd (1982)证明了在一类受限的算法(Strassen 型双线性恒等式和 lambda 计算)中，矩阵乘法有一种弱的加速形式。
== 正式定义 ==
形式上，假设我们有一个下限定理，表明一个问题需要 Ω (f (n))时间来解决一个大小为 n 的实例(输入)(关于 Ω 的定义见大 O 符号大 Ω 符号)。 在此基础上，提出了一种在 O (f (n))时间内求解该问题的渐近最优算法。 这也可以用限制来表示: 假设 b (n)是运行时间的下限，并且给定的算法需要时间 t (n)。 那么算法是渐近最优的，如果:

: <math>\lim_{n\rightarrow\infty} \frac{t(n)}{b(n)} < \infty.</math>

这个极限，如果存在的话，总是至少为1，因为 t (n)≥ b (n)。

虽然通常应用于时间效率，算法可以说是使用渐近最优空间，随机位，处理器数量，或任何其他资源通常使用大 O 符号测量。

有时，模糊或隐含的假设可能会使算法是否渐近最优变得不清楚。 例如，一个下限定理可能假设一个特定的抽象机器模型，比如比较排序，或者一个特定的内存组织。 通过违背这些假设，一个新的算法可能潜在地渐近地优于下界算法和“渐近最优”算法。
== 参考文献 ==
{{reflist}}

[[Category:渐近分析]]

== 参见 ==

* [[元素唯一性问题]]
* {{tsl|Asymptotic computational complexity|渐近运算复杂度}}