檢視大O符號的原始碼

'''大 O 符號'''（英語：Big O notation）， 閣叫做'''漸進符號'''，是用描述函式漸漸行為的數學符號。閣較確切咧講，伊是用另外一个（通常閣較簡單的）函式來描述一个函式數量級的'''漸漸上界'''。佇咧數學中，伊一般提來刻畫被截斷的無窮級數尤其是漸漸級數的賰無夠；佇電腦科學當中，伊咧分析演算法複雜性的方面非常有路用。

大 O 符號是由德國數論學家保羅 ・ 巴赫曼在其一八九二年的對作《解析數論》（_ Analytische Zahlentheorie _）起先引入的。啊若這个記號是佇另外一位德國數論學家愛德蒙 ・ 蘭道的著作中才推廣的，因此伊就是有時閣會叫做'''蘭道符號'''（Landau symbols）。 代表「order of . . .」（……階）的大'''O'''，頭仔是一个大寫希臘字母「Ο」（omicron）， 這馬用的是大寫拉丁字母「O」。

==使用==

===散赤大漸漸近===

大 O 符號咧分析演算法效率的時陣非常有用。比一个例，解決一个規模為 $ n $ 的問題所開的時間（抑是所需要步驟的數目）會當表示講：$ T ( n )=四 n ^ { 二 } 鋪二 n + 二 $。當 $ n $ 增加大時，$ n ^ { 二 } $ 項將開始占主導地位，抑若其他逐項會使予人無注意。比如講：當 $ n=五百 $，$ 四 n ^ { 二 } $ 項嘿 $ 二 n $ 項的一千倍大，所以去大多數場合下，省略以後人對表達式的值的影響將是會使失覺察。

進一步看，若是咱佮任一其他級的表達式較，$ n ^ { 二 } $ 項的係數嘛無關係要緊。比如講：一个包括 $ n ^ { 三 } $ 抑是 $ n ^ { 二 } $ 項的表達式，就算 $ T ( n )=一 , 零 , 零 \ cdot n ^ { 二 } $，假定 $ U ( n )=n ^ { 三 } $，一旦 $ n $ 增加甲真大過 , 零 , 零，後者就會一直超過前者（$ T ( 一 , 零 , 零 )=一 , 零 , 零 ^ { 三 }=U ( 一 , 零 , 零 ) $）。


按呢乎，針對頭一个例 $ T ( n )=四 n ^ { 二 } 鋪二 n + 二 $，大 O 符號就記下賰的部份，寫作：


: $ T ( n ) \ in \ mathrm { O } ( n ^ { 二 } ) $

抑是


: $ T ( n )=\ mathrm { O } ( n ^ { 二 } ) $

而且咱就講該演算法具有 $ n ^ { 二 } $ 階（平方階）的時間複雜度。

===散赤小可仔近===

大 O 嘛會當用來描述數學函式估計中的精差項。比如講 $ e ^ { x } $ 的泰勒展開：


: $ e ^ { x }=一 + x + { \ frac { x ^ { 二 } } { 二 } } + { \ hbox { O } } ( x ^ { 三 } ) \ qquad $ 當 $ x \ to 零 $ 時這表示講，若是 $ x $ 有夠接近佇咧零，遐爾仔精差 $ e ^ { x }-\ left ( 一 + x + { \ frac { x ^ { 二 } } { 二 } } \ right ) $ 的絕對值較細 $ x ^ { 三 } $ 的某一常數倍。

註：泰勒展開的差別 $ r _ { 三 } ( x ) $ 是關於 $ x ^ { 三 } $ 一个高階無窮小量，用小 o 來表示，即：$ r _ { 三 } ( x ) $=$ o ( x ^ { 三 } ) $，也就是講 $ \ lim _ { x \ to 零 } { \ frac { r _ { 三 } ( x ) } { x ^ { 三 } } }=零 . $

==形式化定義==

予定兩个定義佇實數某囝集頂懸的關於 $ x $ 的函式 $ f ( x ) $ 和 $ g ( x ) $，當 $ x $ 較早是散甲無錢大時，存在正實數 $ M $，予對所有充分大的 $ x $，攏有 $ f ( x ) $ 的絕對值小於等於 $ M $ 乘以 $ g ( x ) $ 的絕對值，咱就會當講，當 $ x \ to \ infty $ 時，


: $ f ( x )=\ mathrm { O } ( g ( x ) ) $

也就是講，假使存在正實數 $ M $ 佮實數 $ x $ 零，予對所有的 $ x \ geq x _ { 零 } $，均有：$ | f ( x ) | \ leq \ M | g ( x ) | $ 成立，咱就會當認為講，$ f ( x )=\ mathrm { O } ( g ( x ) ) $。

佇足濟狀況之下，阮會儉起來「當 $ x $ 較近限大時間」這个前提，簡寫為講：


: $ f ( x )=\ mathrm { O } ( g ( x ) ) $

此概念嘛會當用著描述函式 $ f $ 佇接近實數 $ a $ 的時陣的行為，通常 $ a=零 $。當阮講，當 $ x \ to a $ 時，有 $ f ( x )=\ mathrm { O } ( g ( x ) ) $，就相當的出名，當而且干焦當存在的正實數 $ M $ 佮實數 $ \ delta $，予對所有的 $ 零 \ leq | x-a | \ leq \ delta $，均有 $ | f ( x ) | \ leq \ M | g ( x ) | $ 成立。

若做了 $ x $ 和 $ a $ 夠接近的時候，$ g ( x ) $ 的值猶原毋是零，這兩種定義就會當統一用上極限來表示：


: 當而且干焦做 $ \ limsup _ { x \ to a } \ left | { \ frac { f ( x ) } { g ( x ) } } \ right | < \ infty $ 時，有 $ f ( x )=\ mathrm { O } ( g ( x ) ) $。

==例==

佇具體的運用中，阮無一定使用大 O 符號的標準定義，是使用幾條簡化規則來求出關於函式 $ f $ 的大 O 表示：

* 假使講 $ f ( x ) $ 是幾若項之佮，遐爾仔干焦保留增長上緊（通常是階上懸）的項，其他的項省略。
* 假使講 $ f ( x ) $ 是幾項之積，遐爾捷數（攏無決定 x 的乘數）省略。

比如講，使 $ f ( x )=六 x ^ { 四 } 鋪二 x ^ { 三 } + 五 $，阮欲愛用大隻 O 符號來簡化這个函式，來講 $ x $ 將近並無窮大時函式的增長情況。這改函式三項相加成，$ 六 x ^ { 四 } $，$ 鋪二 x ^ { 三 } $ 和 $ 五 $。因為增長上緊的是 $ 六 x ^ { 四 } $ 這一項（因為推上懸嘛，佇咧 x 接近散赤大時，其實對佮的影響會大大超過賰兩項）， 應用第一條規則，猶閣保留伊省略其他兩項。對於 $ 六 x ^ { 四 } $，對兩項相乘而得，$ 六 $ 和 $ x ^ { 四 } $；應用第二條規則，$ 六 $ 是無關係 x 的常數，所以省略仔。最後結果為 $ x ^ { 四 } $，嘛即 $ g ( x )=x ^ { 四 } $。故有：


: 由 $ f ( x )=\ mathrm { O } ( g ( x ) ) $，可得：


: $ 六 x ^ { 四 } 鋪二 x ^ { 三 } + 五=O ( x ^ { 四 } ) $

咱會當將上式擴充做標準定義形式：


: 對任意 $ x \ geq x _ { 零 } $，均有 $ | f ( x ) | \ leq M | g ( x ) | $，也就是講 $ 六 x ^ { 四 } 鋪二 x ^ { 三 } + 五 \ leq M | x ^ { 四 } | $

會用得（粗略）求出 $ M $ 和 $ x _ { 零 } $ 的值得來驗證。使 $ x _ { 零 }=一 $：


: $ { \ begin { aligned } | 六 x ^ { 四 } 鋪二 x ^ { 三 } + 五 | & \ leq 六 x ^ { 四 } + | 二 x ^ { 三 } | + 五 \ \ & \ leq 六 x ^ { 四 } + 二 x ^ { 四 } + 五 x ^ { 四 } \ \ & \ leq 十三 x ^ { 四 } \ end { aligned } } $

故 $ M $ 會當為十三。故兩个攏存在。

==定用的函式階==

下跤是咧分析演算法的時常看著的函式分類列表。所有遮的函式攏處理了 $ n $ 因為強欲無窮大的情形之下，增加生做慢的函式列佇頂懸。$ c $ 是一个任意常數。

==一寡相關的漸漸符號==

大 O 是上定咧使用的較函式的漸漸符號。

==注意==

大 O 符號定定予人誤用：有的作者可能會使用大 O 符號表達大 Θ 符號的含義。所以是按呢看著大 O 符號的時陣先確定其實敢是誤用。

==參看==

* O（拉丁字母）
* 細 o 符號
* 大 Ω 符號
* 大 Θ 符號

==參考文獻==

===參照===

===來源===

==延伸閱讀==

[[分類: 待校正]]