人類對大數缺乏直覺#

• 蘇聯物理學家朗道（Landau）將物理學家分為五級，每一級之間差一個數量級（10 倍）。這個劃分方法同樣適用於各類專業人士
• 喬布斯曾說沃茲尼亞克一個人能頂 50 個工程師——人與人水平的差別常常是數量級的
• 人們天生對大數沒有概念，因為我們生活在一個「小數的世界」裡；同樣，對計算機的高速度也是無感的，因為我們生活在一個「很慢的世界」裡

作者的親身經歷#

作者在大學暑假實習時體會到算法效率的重要性：一個財務軟體的對賬模塊由於採用了笨辦法（數據量大 10 倍，對賬時間比原來多出好幾十倍），最初幾秒就完成的對賬變成了半小時。最後請當地的同學修改了十幾行代碼，問題就解決了。

大數的例子#

例題 1.1：圍棋有多複雜？#

• 棋盤上每個點有黑、白、空三種情況，361 個交叉點，變化最多可達 3^361 ≈ 2 × 10^172 種
• 整個宇宙中不過才有 10^79 ~ 10^83 個基本粒子
• 即使把每個基本粒子都變成一個宇宙，再把所有粒子數一遍，數量也沒有圍棋盤上各種變化的總數大

例題 1.2：一句 20 個單詞的英語語句有多少種組合？#

• 英語的單詞數在 10 萬個以上，20 個單詞不限制的組合數是 10^100
• 這個數就是古戈爾（Googol），也比宇宙中基本粒子的數量要多得多
• 語音識別本質上就是在巨大的多維空間中搜索一個點的問題

大 O 概念的定義#

• 上面的大數儘管很大，但仍是實實在在的有限的數，而非無窮大
• 計算機面對的常常是 N 趨近於無窮大時的問題，因此討論算法複雜度時，只考慮 N 趨近於無窮大時和 N 相關的部分
• 我們可以把一種算法的計算量或者占用空間的大小寫成 N 的一個函數 f(N)
• 大 O 的數學定義：如果兩個函數 f(N) 和 g(N) 在 N 趨近於無窮大時比值只差一個常數，那麼它們就被看成同一個數量級的函數，在計算機科學中被認為是具有相同的複雜度
• 如果一個算法的複雜度由一高一低的兩部分 f(N) 和 g(N) 組成，低數量級的部分可以直接省略，即 O(f(N)+g(N))=O(f(N))

這個「西瓜加上兩粒芝麻還等於原來的西瓜」在數學上顯然不成立，但在計算機算法學中是被認可的。其目的是讓計算機科學家能夠把注意力放在數量級的差異上。

要點#

• 複雜度、數量級、大 O 的概念
• 衡量算法好壞的關鍵是看隨 N 增長的數量級，而非具體常數