漸進最優

在計算機科學中，漸進最優一詞用以評價算法的效率。如果已經證實一個問題需要使用Ω(f(n))的資源來解決，而某個算法用O(f(n))的資源來解決這個問題，則該算法就是漸進最優的。

漸進最優的例子包括數據結構動態數組^[1]，能夠在常數時間內索引，但性能在多數機器上不如普通數組的索引。另外，在所有基於比較的排序算法中，歸併排序和堆排序是漸進最優的^{[2]:282, 326}。

加速

漸近最優算法的不存在性稱為加速比。 布魯姆加速定理表明存在人為構造的加速問題。 然而，目前許多最著名的算法是否是漸近最優的，這是一個公開的問題。 例如，有一種算法可以找到最小生成樹，這是一個非常緩慢增長的阿克曼函數，但是最著名的下界是微不足道的。${\displaystyle O(n\alpha (n))}$${\displaystyle \alpha (n)}$${\displaystyle \Omega (n)}$ 這個算法是否是漸近最優的是未知的，如果它被解決了，可能會被歡呼為一個重要的結果。 Coppersmith 和 Winograd (1982)證明了在一類受限的算法(Strassen 型雙線性恆等式和 lambda 計算)中，矩陣乘法有一種弱的加速形式。

正式定義

形式上，假設我們有一個下限定理，表明一個問題需要 Ω (f (n))時間來解決一個大小為 n 的實例(輸入)(關於 Ω 的定義見大 O 符號大 Ω 符號)。 在此基礎上，提出了一種在 O (f (n))時間內求解該問題的漸近最優算法。 這也可以用限制來表示: 假設 b (n)是運行時間的下限，並且給定的算法需要時間 t (n)。 那麼算法是漸近最優的，如果:

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

這個極限，如果存在的話，總是至少為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.

參見

• 元素唯一性問題
• 漸近運算複雜度（：渐近运算复杂度）