渐进最优

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

渐进最优的例子包括数据结构动态数组，能够在常数时间内索引，但性能在多数机器上不如普通数组的索引。另外，在所有基于比较的排序算法中，归并排序和堆排序是渐进最优的。

加速

渐近最优算法的不存在性称为加速比。 布鲁姆加速定理表明存在人为构造的加速问题。 然而，目前许多最著名的算法是否是渐近最优的，这是一个公开的问题。 例如，有一种算法可以找到最小生成树，这是一个非常缓慢增长的阿克曼函数，但是最著名的下界是微不足道的。$O(n\alpha (n))$$\alpha (n)$$\Omega (n)$ 这个算法是否是渐近最优的是未知的，如果它被解决了，可能会被欢呼为一个重要的结果。 Coppersmith 和 Winograd (1982)证明了在一类受限的算法(Strassen 型双线性恒等式和 lambda 计算)中，矩阵乘法有一种弱的加速形式。

正式定义

形式上，假设我们有一个下限定理，表明一个问题需要 Ω (f (n))时间来解决一个大小为 n 的实例(输入)(关于 Ω 的定义见大 O 符号大 Ω 符号)。 在此基础上，提出了一种在 O (f (n))时间内求解该问题的渐近最优算法。 这也可以用限制来表示: 假设 b (n)是运行时间的下限，并且给定的算法需要时间 t (n)。 那么算法是渐近最优的，如果:

$\lim _{n\rightarrow \infty }{\frac {t(n)}{b(n)}}<\infty .$

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

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

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

参见

• 元素唯一性问题
• 渐近运算复杂度