我們開始了算法復(fù)雜度的學(xué)習(xí)，本期教程我們學(xué)習(xí)后半段。
復(fù)雜度只考慮操作數(shù)目的一個數(shù)量級（忽略了其他的組分），這是一種近似。
為了表示這種近似，我們使用一個特定的符號，就是著名的 大 O 符號。
大 O 符號（Big O notation），又稱為漸進符號，是用于描述函數(shù)漸近行為的數(shù)學(xué)符號。更確切地說，它是用另一個（通常更簡單的）函數(shù)來描述一個函數(shù)數(shù)量級的漸近上界。在數(shù)學(xué)中，它一般用來刻畫被截斷的無窮級數(shù)尤其是漸近級數(shù)的剩余項。在計算機科學(xué)中，它在分析算法復(fù)雜度的方面非常有用。大 O 符號是由德國數(shù)論學(xué)家 保羅·巴赫曼（Paul Bachmann）在其 1892 年的著作《解析數(shù)論》（Analytische Zahlentheorie）首先引入的。而這個記號則是在另一位德國數(shù)論學(xué)家 艾德蒙·朗道（Edmund Landau）的著作中才推廣的，因此它有時又稱為 朗道符號（Landau Notation）。代表“order of …”（…階）的大 O，最初是一個大寫希臘字母“Ο”（Omicron），現(xiàn)今用的是大寫拉丁字母“O”。
例如，小鴨子們?nèi)ザ燃龠@個故事里，農(nóng)夫 Oscar 的第一種算法有 N2 個操作，我們就說此算法的復(fù)雜度是 O(N2)。類似地，第二種更快的算法的復(fù)雜度是 O(N)。
大 O 符號有點像一個大圓形的袋子，可以把不同的操作數(shù)目整合在一起，使之具有一個同樣的數(shù)量級。
例如，如果有三個算法，它們的操作數(shù)目分別為 N，5N + 7 和 N / 4，我們就都用 O(N) （讀作 “N 的 大 O”。當然了，讀法其實不是那么固定）來表示這三個算法的復(fù)雜度。
類似地，如果一個算法的操作數(shù)是（2 * N2 + 5 * N + 7），那么它的復(fù)雜度是 O(N2)：我們忽略了 5 * N 和 7 這兩項，因為它們與 2N2 相比數(shù)量級較小。隨著 N 的增大，這兩項的增長速率比 2N2 要慢，因此我們保留 2N2 即可，又因為常數(shù)乘法因子（這里是 2）不予考慮，因此記為 O(N2)。
我們說 f(N) 表示“N 的函數(shù)”（例如， f(N) = 2 * N2 + 5 * N + 7) ），那么 O(f(N)) 表示的是“大約有 f(N) 個操作的算法的復(fù)雜度”，這里的“大約”是非常關(guān)鍵的。
2. 時間復(fù)雜度和空間復(fù)雜度
下面我們來學(xué)習(xí)算法中常聽到的“時間復(fù)雜度”和“空間復(fù)雜度”。
為什么我竟然想到了漫威里面的大反派滅霸的無限手套呢？上面有時間寶石和空間寶石這兩顆無限寶石。一定是因為我看了《復(fù)仇者聯(lián)盟3：無限戰(zhàn)爭》和《復(fù)仇者聯(lián)盟4：終局之戰(zhàn)》的關(guān)系…
重慶分公司
重慶分公司
