跳至內容

漸進最優

維基百科,自由的百科全書

計算機科學中,漸進最優一詞用以評價算法的效率。如果已經證實一個問題需要使用Ω(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. 

參見

[編輯]