渐进最优

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

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