大O符號(英語:Big O notation),又稱為漸進符號,是用於描述函式漸近行為數學符號。更確切地說,它是用另一個(通常更簡單的)函式來描述一個函式數量級漸近上界。在數學中,它一般用來刻畫被截斷的無窮級數尤其是漸近級數的剩餘項;在電腦科學中,它在分析演算法複雜性的方面非常有用。

大O符號是由德國數論學家保羅·巴赫曼在其1892年的著作《解析數論》(Analytische Zahlentheorie)首先引入的。而這個記號則是在另一位德國數論學家愛德蒙·蘭道的著作中才推廣的,因此它有時又稱為蘭道符號(Landau symbols)。代表「order of ...」(……階)的大O,最初是一個大寫希臘字母Ο」(omicron),現今用的是大寫拉丁字母O」。

使用

編輯

無窮大漸近

編輯

大O符號在分析演算法效率的時候非常有用。舉個例子,解決一個規模為 的問題所花費的時間(或者所需步驟的數目)可以表示為: 。當 增大時, 項將開始占主導地位,而其他各項可以被忽略。舉例說明:當  項是 項的1000倍大,因此在大多數場合下,省略後者對表達式的值的影響將是可以忽略不計的。

進一步看,如果我們與任一其他級的表達式比較, 項的係數也是無關緊要的。例如:一個包含  項的表達式,即使 ,假定 ,一旦 增長到大於1,000,000,後者就會一直超越前者( )。


這樣,針對第一個例子 ,大O符號就記下剩餘的部分,寫作:

 

 

並且我們就說該演算法具有 階(平方階)的時間複雜度

無窮小漸近

編輯

大O也可以用來描述數學函式估計中的誤差項。例如 泰勒展開

  

這表示,如果 足夠接近於0,那麼誤差 絕對值小於 的某一常數倍。

註:泰勒展開的誤差餘項 是關於 一個高階無窮小量,用小o來表示,即: = ,也就是 

形式化定義

編輯

給定兩個定義在實數某子集上的關於 的函式  ,當 趨近於無窮大時,存在正實數 ,使得對於所有充分大英語sufficiently large ,都有 的絕對值小於等於 乘以 的絕對值,那麼我們就可以說,當 時,

 

也就是說,假如存在正實數 和實數 0,使得對於所有的 ,均有: 成立,我們就可以認爲, 

在很多情況下,我們會省略「當 趨近於無限大時」這個前提,而簡寫爲:

 

此概念也可以用於描述函式 在接近實數 時的行爲,通常 。當我們說,當 時,有 ,也就相當於稱,若且唯若存在正實數 和實數 ,使得對於所有的 ,均有 成立。

如果當  足夠接近時, 的值仍不爲0,這兩種定義就可以統一用上極限來表示:

若且唯若 時,有 

例子

編輯

在具體的運用中,我們不一定使用大O符號的標準定義,而是使用幾條簡化規則來求出關於函式 的大O表示:

  • 假如 是幾項之和,那麼只保留增長最快(通常是階最高)的項,其他項省略。
  • 假如 是幾項之積,那麼常數(不取決於x的乘數)省略。

比如,使 ,我們想要用大O符號來簡化這個函式,來描述 接近無窮大時函式的增長情況。此函式由三項相加而成,   。由於增長最快的是 這一項(因為階最高,在x接近無窮大時,其對和的影響會大大超過其餘兩項),應用第一條規則,保留它而省略其他兩項。對於 ,由兩項相乘而得,  ;應用第二條規則, 是無關x的常數,所以省略。最後結果為 ,也即 。故有:

 ,可得:
 

我們可以將上式擴充為標準定義形式:

對任意 ,均有 ,也就是 

可以(粗略)求出  的值來驗證。使 

 

 可以為13。故兩者都存在。

常用的函式階

編輯

下面是在分析演算法的時候常見的函式分類列表。所有這些函式都處於 趨近於無窮大的情況下,增長得慢的函式列在上面。 是一個任意常數。

符號 名稱
  常數(階,下同)
  對數
  多對數
  線性,次線性
   迭代對數
  線性對數,或對數線性、擬線性、超線性
  平方
  多項式,有時叫作「代數」(階)
  指數,有時叫作「幾何」(階)
  階乘,有時叫做「組合」(階)

一些相關的漸近符號

編輯

大O是最經常使用的比較函式的漸近符號。

符號 定義
  漸近上限
  Asymptotically negligible漸近可忽略不計( 
  漸近下限(若且唯若 
  Asymptotically dominant漸近主導(若且唯若 
  Asymptotically tight bound漸近緊約束(若且唯若  

注意

編輯

大O符號經常被誤用:有的作者可能會使用大O符號表達大Θ符號的含義。因此在看到大O符號時應首先確定其是否為誤用。

參看

編輯

參考文獻

編輯

參照

編輯

來源

編輯
書籍
  • 嚴蔚敏、吳偉民:《資料結構:C語言版》. 清華大學出版社,1996. ISBN 7-302-02368-9. 1.4節 演算法和演算法分析,pp. 14-17.
  • 朱青:《計算機演算法與程式設計》. 清華大學出版社,2009.10。ISBN 978-7-302-20267-7. 1.4節 演算法的複雜性分析,pp. 16-17.

延伸閱讀

編輯