### 10.5.1 算法復雜度 為了回答上述問題，首先要明確如何衡量算法的好壞。以搜索問題為例，線性搜索算法 直接了當，易設計易實現，這算不算“好”？而二分搜索算法雖然設計實現稍難一些，但因 無需檢查每一個數據而大大提高了搜索效率，這又算不算“好”？ 在解決數學問題時，不論是證明定理還是計算表達式，只要證明過程正確、計算結果精 確，問題就可以認為成功地解決了，即正確性、精確性是評價數學解法好壞的標準。而在用 計算機解決問題時，僅僅要求算法能正確、精確地解決問題，是不夠的。試想，假如一個算 法雖然能夠正確地解決問題，但需要在計算機上運行 100 年或者需要占用 100TB 的內存， 這樣的算法有實際意義嗎？不要以為 100 年或 100TB 是危言聳聽，很多簡單算法都可能輕 易地達到或突破這樣的需求（參見稍后對 Hanoi 塔算法的分析）。可見，利用計算機解決問 題必須考慮算法的經濟性，即算法所耗費的資源問題。計算機用戶當然都希望能多快好省地 解決問題，因此好的算法應當盡量少地耗費資源。 通常只考慮算法所占用的 CPU 時間和存儲器空間這兩種資源①。所謂算法分析，就是分 析特定算法在運行時所耗費的時間和存儲空間的數量，分別稱為算法的時間復雜度和空間復 雜度。本節只討論算法的時間復雜度，畢竟存儲空間的大小在現代計算機中已經越來越不再 是一個問題。 雖然討論的是算法耗費的“時間”，但我們并不是真的去測量程序在計算機中的實際運 行時間，因為實際運行時間依賴于特定機器平臺（CPU、內存、操作系統、編程語言等）， 同一算法在不同平臺上執行可能得到不同的分析結果，故很難據此對算法進行分析和比較。 例如，在最先進的計算機上執行線性搜索也許比在老式計算機上執行二分搜索要快，據此得 出線性搜索優于二分搜索顯然不合理。 實際上，算法分析指的是分析算法的代碼，估計出為解決問題需要執行的操作（或語句、 指令等類似概念）的數目，或稱算法的“步數”。之所以分析算法步數，是因為：第一，步 數確實能反映執行時間——步數越多執行時間就越長；第二，算法的步數不依賴于平臺，更 容易分析和比較。 例如，下面的函數 f1()需要執行 11 次賦值操作，其中包含 10 次加法運算②： ``` def f1(): x = 0 for i in range(10): x = x + 1 ``` 而下面的函數 f2()需要 21 次賦值操作（20 次加法）： ``` def f2(): x = 0 for i in range(20): x = x + 1 ``` 比較一下 f1 和 f2，顯然 f1 運行時間更短，但這并不意味著 f1 比 f2 采用的算法“好”， 因為它們的“算法”顯然是一樣的，只不過 f1 要處理的數據更少：f1 將 10 個 1 相加，而 f2 將 20 個 1 相加。可見，算法復雜度是跟算法處理的數據量有關的。 算法通常都設計成能處理任意大小的輸入數據，這就導致算法的步數并不是固定的，而 是隨著問題規模的變化而變化，因此算法的步數可表示為問題規模的函數。假設用 n 表示問題規模，算法分析不僅要考慮算法步數與 n 的關系，更重要的是還要考慮“當 n 逐漸增大時” 算法復雜度會如何變化。例如，將上述 f1 和 f2 改寫成更一般的形式： > ① 不考慮開發算法的人力物力等代價。 > ② 注意我們分析的層次是源代碼級別，而不是機器指令級別。 ``` def f(n): x = 0 for i in range(n): x = x + 1 ``` 不難得出此函數需要執行的步數為 n+1。當 n 增大時，算法執行時間也會增加，而且是線性地增加，即：當 n 增加 1 倍變成 2n，執行時間變成 2n+1，大約比 n+1 增加 1 倍。 說 A 算法比 B 算法好，并不是指對于特定的 n，A 比 B 節省 50%的時間，而是指隨著 n 的不斷增大，A 對 B 的優勢會越來越大。 算法復雜度的大 O 表示法 再次觀察上面例子中函數 f()的步數表達式“n+1”，不難看出其中對執行時間起決定作 用的是 n，而 n 后面的+1 是可以忽略不計的。按照“當 n 逐漸增大時”進行分析的思想， 即便是 n+100、n+1000000 中，n 后面的常數也是可以忽略不計的，因為與逐漸增大趨于∞ 的 n 相比，任何常數都是浮云。事實上，分析算法復雜度時，我們只分析其增長的數量級， 而不是分析其精確的步數公式。 數學中的“大 O 表示法”根據函數的增長率特性來刻畫函數，可以用來描述算法的復 雜度。令 f(n)和 g(n)是兩個函數，如果存在正常數 c，使得只要 n 足夠大（例如超過某個 n0）， 函數 f(n)的值都不會超過 c×g(n)，即當 n &gt; n0 時， ``` f(n) <= c x g(n) ``` 則可記為 ``` f (n) = O(g(n)) ``` 在描述算法復雜度時，n 對應于問題規模，f(n)是算法需執行的步數，g(n)是表示增長數 量級的某個函數。說算法的復雜度為 O(g(n))，意思就是當 n 足夠大時，該算法的執行步數（時間）永遠不會超過 c×g(n)。 例如，假設一個算法當輸入規模為 n 時需要執行 n+100 條指令，則當 n 足夠大時（只 要大于 100）， ``` n + 100 <= n + n = 2n ``` 套用大 O 表示法的定義，取 g(n)=n，則可將此算法的復雜度表示為 O(n)。同理，如果一個 算法的步數為 n+1000000，它的復雜度仍然可表示為 O(n)。由此可見，兩個不同的算法雖然 具有不同的代碼和執行步數，但完全可能具有相同的復雜度，即當問題規模足夠大時，它們 的執行時間按相同數量級的增長率增長，利用大 O 表示法即可描述這一點。 實際分析算法時，為了使 O(g(n))中的 g(n)函數盡量簡單，在得到算法的步數表達式 f(n) 之后，可以利用兩條規則來簡化推導，直接得出 f(n)的大 O 表示。規則如下： （1）如果 f(n)是若干項之和，則只需保留最高次項，省略所有低次項； （2）如果 f(n)是若干項之積，則可省略任何常數因子（即與 n 無關的因子）。 例如，分析下列代碼： ``` def f(n): x = 0 for i in range(n): for j in range(n): for k in range(n): x = x + 1 for i in range(n): for j in range(n): for k in range(n): x = x + 1 for i in range(n): x = x + 1 ``` 易知此算法的步數為 2n³+n+1。根據第一條規則，可只保留 2n3；再根據第二條規則，可只保留 n³。所以，此算法的復雜度為 O(n³)。當然我們也可以直接從 f(n)開始推導，利用大 O表示法的定義來驗證這個結果是正確的：對于 n &gt; 1，  取 g(n)為 n3，c 為 4，即得 f(n) = O(n3)。 總之，以上兩條規則告訴我們，在分析算法代碼時可以忽略許多代碼，而只關注那些嵌套層數最多、并且每一層循環的循環次數都與問題規模 n 有關的循環。