大O符號

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

大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.

延伸閱讀[編輯]