### 10.5.2 算法分析實例 本節以本章介紹的若干算法為例來討論對算法復雜性的分析。 搜索問題的兩個算法 對于搜索問題，本章介紹了線性搜索和二分搜索兩個算法。 線性搜索算法的思想是逐個檢查列表成員，編碼時可以用一個循環語句來實現。循環體 的執行次數取決于列表長度：如果列表長度為 n，則循環體最多執行 n 次。因此，如果列表 長度增大一倍，則循環次數最多增加一倍，算法執行的步數或實際運行時間最多增加一倍。 可見，線性搜索算法在最壞情形下的運行時間與輸入列表的大小 n 呈線性關系，即復雜度為 O(n)，稱為線性時間算法。 二分搜索算法的主體也是一個循環，但該循環不是逐個檢查列表數據，而是每次檢查位 于列表中點的數據，并根據該中點數據與要查找的數據的大小比較情況來排除掉左半列表或 右半列表。接著對保留下來的一半列表重復進行這個“折半”過程。顯然，循環的次數取決 于輸入列表能“折半”多少次。如果初始輸入列表有 16 個數據，則第一輪循環后剩下 8 個數據，第二輪循環后剩下 4 個數據，第三輪后剩下 2 個，第四輪后只剩下 1 個數據。因此， 最多四輪循環后就能得出搜索結論：要么找到，要么不存在。一般地，如果輸入規模為 n， 則二分搜索算法最多循環 log2n 次，即復雜度為 O(log2n)，稱為對數時間算法。要說明的是， O(log2n)表示復雜度與問題規模 n 的對數成正比，至于這個對數是以 2 為底還是以 10 為底并 不重要，因此我們經常省略對數的底，寫成 O(log n)。 O(n)與 O(log n)到底有多大差別？回到 10.2 中提到的猜數游戲，假如某甲心中想好一個1百萬以內的數讓某乙來猜。某乙從小到大逐個試猜（即線性搜索）的話，運氣好猜 1 次就能命中，運氣不好最多要猜 1 百萬次。平均來說需要猜 50 萬次才能猜中。而如果某乙每次 猜中間數（即二分搜索）的話，則最少猜 1 次，最多也不過猜 log21000000≈20 次就能猜中。 可見，隨著 n 的增大，O(log n)遠遠優于 O(n)。 排序問題的兩個算法 對于排序問題，本章介紹了選擇排序和歸并排序兩個算法。 首先推導選擇排序算法的步數與問題規模（即數據列表的長度）的關系。選擇排序算法 首先找出全體數據中的最小值，并將該值作為結果列表的第一個成員。其次，算法從剩余數 據中找出最小值，并將該值作為結果列表的第二個成員。依此類推，直至產生有序列表。假 設列表初始大小為 n，為找出最小值，算法需檢查每一個數據。接下來算法從剩余 n-1 個數 據中找出最小值，這需要檢查 n-1 個數據；第三次循環從 n-2 個剩余數據中找出最小值。這 個過程一直繼續到只剩 1 個數據為止。因此，選擇排序需要執行的步數為  按照前述規則，可以看出選擇排序算法所需的步數與數據列表大小的平方成正比，即算法復雜度為 O(n²)，稱為二次方時間算法。 其次，我們來推導歸并排序算法的步數與列表大小的關系。歸并排序算法的基本思想是將列表一分為二，然后對兩半數據各自排序，最后再合并成一個列表。其中對兩個子列表的 排序又是通過遞歸調用歸并排序來實現的，最終將分解到長度為 1 的列表，這時可直接進行 歸并。由此可見真正的排序工作是在歸并過程中完成的，該過程所做的只是將來自子列表的 數據按從小到大的順序逐個復制到初始列表的合適位置。圖 10.11 展示了對列表[0,5,7,2]進 行歸并排序的過程。圖中用虛線表示初始列表的遞歸分解過程，逐步分解后最終得到長度為 1 的列表。這些長度為 1 的列表再進行歸并，逐步形成長度為 2、4 的有序的列表，圖中用實線箭頭表示歸并時各數據的逐步到位過程。從圖 10.11 容易分析出歸并排序算法的步數。 從左向右，分解過程并不比較數據大小來排序，這部分工作可以忽略。接下來的歸并過程包 含大量比較、復制操作，是整個算法的工作量的體現。歸并過程分為 log2n 層，以逐步形成 長度為 2、22、23、…、n 的有序子列表①。又因為每一層歸并都需要對全部 n 個數據進行處 理，所以歸并排序算法的步數是“n×層數”，即具有復雜度 O(nlog n)，可稱為 nlog n 時間 算法。  圖 10.11 歸并排序過程示意圖 n² 與 nlog n 有多大差別呢？當 n 較小時，兩者差距不大，選擇排序算法甚至有可能還快 一些，因為它的代碼更簡單。但是，隨著 n 的增大，log n 只是緩慢地增大，因此 n×log n 的增長速度遠遠低于 n×n。這就是說，對于大量數據，歸并排序算法的性能遠遠好于選擇 排序算法。 > ① 如果 n 不是 2 的冪，子列表的長度當然也不會都是 2 的冪。 Hanoi 塔算法 下面推導 Hanoi 塔問題的遞歸算法的步數與圓盤個數 n 的關系。與基于循環（迭代）的算法不同，遞歸算法不容易直接從代碼形式上看出具體的操作步數。對于 Hanoi 塔遞歸算法， 我們可以直接考慮將 n 個圓盤從 A 柱移到 C 柱所需的移動次數。 根據算法的結構，為了移動 n 個圓盤，需要先將 n-1 個圓盤從最大圓盤上移開，然后移 動最大圓盤，最后再將 n-1 個圓盤移到最大圓盤上。假設 f(n)是移動 n 個圓盤所需的步數， 則應用一點中學數學知識很容易推導出  可見，Hanoi 塔算法的復雜度為 O(2n)，稱為指數時間算法，這是因為問題規模的度量 n 出 現在步數公式的指數部分。 指數時間算法到底有多復雜呢？讀者也許聽說過“指數爆炸”這個名詞，它表明指數時 間算法所需要的執行時間會隨著問題規模的增長而迅速增長。在 Hanoi 塔故事中，即使僧侶 們 1 秒鐘就能移動一步圓盤，并且每天都不休息，為了移動 64 個圓盤，也需要花費 264－1秒，即 5850 億年！可見，指數時間算法只適用于解決小規模的問題。 總之，利用計算機解決問題時，需要考慮算法的時間復雜性，這是衡量問題難度和算法 優劣的一個重要指標。有些應用對于運行時間有較高要求，運行時間過長的話可能導致計算 結果過時、失效。圖 10.12 給出了本章見過的各種算法復雜度的大致比較，圖中橫坐標表示 問題規模 n，縱坐標是算法執行時間（或步數）。雖然圖中曲線不是很精確，但足以說明指 數時間和二次方時間算法是多么不適合大量數據，而其他幾種復雜度的曲線則相當平緩。  圖 10.12 各種算法復雜度比較