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

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

加速

编辑

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

正式定义

编辑

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

 

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

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

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

参考文献

编辑
  1. ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED, Resizable Arrays in Optimal Time and Space (PDF), Department of Computer Science, University of Waterloo, 1999 [2019-05-12], (原始内容存档 (PDF)于2020-10-29) 
  2. ^ Robert Sedgewick; Kevin Wayne. Algorithms 4th. Addison-Wesley. ISBN 978-0-321-57351-3. 

参见

编辑