渐进最优 (asymptotically optimal) 这个名词看到很多次了，在这篇博客总结一下这个概念。

一个算法的复杂度，在输入值无限大时，与已知的最优算法的复杂度相比（相除），为一个常数，则该算法为渐进最优算法。

更加正式的定义是：

若最优算法的运行时间下界为 $b(n)$, 其中 $n$ 为输入值的大小，当前算法的运行时间为 $t(n)$. 若
$$\underset{n\to \infty }{\lim }\frac{t(n)}{b(n)}<\infty$$
的极限存在（若存在，极限值为1），则该算法为渐进最优算法。

例如，最优的排序算法的复杂度为 $O(n\lg n)$，而堆排序与归并排序的算法复杂度都是 $O(n\lg n)$，因此这两个算法为渐进最优。