第四百七十五章 保羅·巴赫曼的大O符號（微積分）

　　大O符號是由德國數(shù)論學(xué)家保羅·巴赫曼（Paul Bachmann）在其1892年的著作《解析數(shù)論》引入。

　　保羅·巴赫曼在計算工程問題的時候，找到了一個公式，然后對這些公式產(chǎn)生了疑惑。

　　然后找到了一個無窮大漸進(jìn)和無窮小漸進(jìn)的一個表示，認(rèn)為這個表示有一定的重要性了。

　　保羅·巴赫曼找到了埃德蒙·朗道開始討論這個問題。

　　巴赫曼說：“解決一個規(guī)模為 n 的問題所花費(fèi)的時間，也就是所需步驟的數(shù)目，可以被求得?！?p>　　巴赫曼寫出了公式T(n)= 4n^2 - 2n + 2，給朗道看。

　　巴赫曼繼續(xù)說：“當(dāng) n 增大時，n^2;項將開始占主導(dǎo)地位，而其他各項可以被忽略——舉例說明：當(dāng) n = 500，4n^2;項是 2n 項的1000倍大，因此在大多數(shù)場合下，省略后者對表達(dá)式的值的影響將是可以忽略不計的?！?p>　　朗道說：“然后，是不是尾巴拖著難受？”

　　巴赫曼說：“進(jìn)一步看，如果我們與任一其他級的表達(dá)式比較，n^2;項的系數(shù)也是無關(guān)緊要的。例如一個包含 n^3;或 n^2項的表達(dá)式，即使 T(n)= 1，000，000n^2;，假定 U(n)= n^3;，一旦 n 增長到大于1，000，000，后者就會一直超越前者(T(1，000，000)= 1，000，000^3;= U(1，000，000))?！?p>　　朗道說：“沒錯，當(dāng)年的2次方是最重要的，但3次方擠進(jìn)來，居然就叫不重要了。讓人頭疼?！?p>　　巴赫曼說：“誰說不是呢！肯定得需要想個辦法才對啊。”

　　朗道說：“我們需要對剩下的尾巴打包處理才行?！?p>　　巴赫曼說：“我們對這個量定義階這樣的概念吧，就是order of 中開頭O這個部分，當(dāng)然來源于希臘語Omicrond開頭，我們叫他大O?！?p>　　朗道說：“是的，可以表示無窮大或無窮小的漸近?！?