電腦真的夠快了嗎

現代電腦科技發展迅速，電腦的運算能力也愈來愈強大。如果按照摩爾定律的推論，IC 上可容納的電晶體數目，每隔約 18 個月便可以增加一倍，因而電腦的性能每隔 18 個月也會跟著增加一倍，那麼換句話說，電腦的性能就不只是呈現線性而是呈指數的速度在成長。聽過阿基米德故事的人都應該知道，這種指數的成長速度是相當驚人的，但是回過頭來仔細思考，摩爾定律的基礎是建構在 IC 上電晶體的數量，試想如果不斷地在一塊小小的 IC 晶片上塞進大量的電晶體，到最後會是什麼結果？摩爾定律的提出者，戈登．摩爾說:「任何指數函數一旦外推到一定程度都會遇到阻礙。物質由原子構成這一事實就是根本的局限所在。我們不可能做得更小了。」* 這一番話說明了摩爾定律最終還是會失效的，那麼當摩爾定律失效以後，電腦未來的發展該何去何從？

演算法的效率

曾聽過幾位寫程式的朋友告訴我:「現在電腦跑得這麼快，程式就算寫得不好、沒做最佳化 (optimization)，一樣還是可以跑得很快」類似這樣的話。的確，在許多情況下確實是如此，電腦的執行速度快到讓一些多餘程式碼所造成的延遲微小到無法被察覺，特別是一些比較簡單的小程式。不過有學過演算法的人應該會了解，在某些情況下如果程式沒有用對演算法，那麼不管電腦執行的速度再怎麼快，仍舊是杯水車薪，無法讓一個程式在合理的時間內執行完畢的。就舉我們常用的排序來說，以插入排序法排序 n 個項目平均大約需要做 n² 次比較，因此平均的時間複雜度 (time complexity) 為 O(n²) (見 big O notation)；而以快速排序法排序 n 個項目平均大約需要做 n log₂(n) 次比較，因此平均的時間複雜度為 O(n log₂(n))。相較於快速排序法，插入排序法是一種頗為直觀而且簡單的排序方式，對於比較沒有演算法及排序背景知識的程式設計師而言，他可能會直覺地實作出插入排序法來完成程式中排序的任務。當排序項目的數量 n 不大時，使用插入排序法來排序是沒有問題的，但是當 n 大於某數時 (視電腦的執行速度而定)，插入排序法的效能便開始有了戲劇性的轉變。

圖 1: n、n log2(n) 與 n2 之比較 (n 在 1 到 101 之間)。

n n2 (插入排序) n log2(n) (快速排序) 1 1 0 11 121 38.05 21 441 92.24 31 961 153.58 41 1681 219.66 51 2601 289.29 61 3721 361.77 71 5041 436.63 81 6561 513.53 91 8281 592.21 101 10201 672.48 表 1

為比較插入排序與快速排序，我們取樣一些數據製成表 1 並將對應的曲線繪製在圖 1 中，其中橫軸代表 n，縱軸代表比較的次數。由圖中我們可以看到插入排序法 (紅色) 隨著 n 值的遞增而快速地發散，而快速排序法 (綠色) 的發散速率則慢了許多，並且比較接近線性 (藍色) 的走向。由表中我們可以看出當 n = 11 時插入排序法所需要的比較次數約是快速排序法的 3 倍，然而當 n = 101 時所需要的比較次竟是快速排序法的 15 倍之多。如果我們把 n 的範圍再加大，如表 2 及圖 2 所示，我們可以看到更大的差距。當 n = 1001 時插入排序法所需要的比較次數將會是快速排序法的 100 倍左右，假設快速排序法排序 1001 項目所需的時間為 0.1 秒，那麼插入排序法排序 1001 項目將需要 10 秒鐘的時間。由此可知，在某些情況下演算法的不同或是程式設計上的不同，在程式執行的效率上將造成極大的差別。

圖 2: n、n log2(n) 與 n2 之比較 (n 在 1 到 1001 之間)。

n n2 (插入排序) n log2(n) (快速排序) 1 1 0 101 10201 672.48 201 40401 1537.86 301 90601 2478.32 401 160801 3467.63 501 251001 4493.3 601 361201 5547.96 701 491401 6626.74 801 641601 7726.17 901 811801 8843.66 1001 1002001 9977.19 表 2

演算法的極限

除了演算法的選擇會影響到程式的執行效率以外，仍有許多問題至今即使運用已知最快的演算法，當問題的 n 值較大時甚至連得到解答的希望都沒有。例如著名的旅行推銷員問題 (Traveling Salesman Problem, TSP):

有 n 個城市，一個推銷員要從其中某一個城市出發，並造訪所有的城市，再回到他出發的城市，在造訪的過程中行經的路線不能重覆，請問推銷員要如何造訪這些城市才能以最短的路線走完全程？

解決 TSP 其中的一個辦法是運用窮舉法，由於所有可能的路線線共有 (n－1)! 種排列方式，因此窮舉法的時間複雜度為 O(n!)，如果改用動態規劃 (Dynamic Programming)，我們可以將解題的時間複雜度降為 O(n²2ⁿ)，雖然比 O(n!) 好很多但是仍比之前提到的插入排序法 O(n²) 差上許多，只要 n 值稍微大一點，一般的電腦便無法應付如此龐大的計算量，所以 TSP 也被歸類為 NP-hard 問題。O(n²2ⁿ) 的複雜度甚至比前面阿基米德故事裡提到的米粒數量 O(2ⁿ) 發散得還要快，只不過一個指的是時間複雜度而另一個指的是米粒的數量，也算是另一種空間複雜度 (space complexity) 吧。以目前的計算機科技而言，或許還能應付多項式時間 (polynomial time) O(n^k) 以內的演算法，其中 k 為一大於或等於 2 的常數，但是對於複雜度的等級大於多項式時間再加上一個大一點的 n 則毫無希望。

計算機的發展

綜合以上的論述，我們可以看到以半導體元件為基礎的計算機，在許多應用上仍有很大的限制。從 BOINC 的項目中我們就可以看到許多這樣的應用，這些項目的共同點就是都需要進行一些計算量龐大的工作。藉由 BOINC 這個分散式的平台，希望能夠募集世界各地自願者所提供的電腦運算能力，來執行各項大計算量的研究計畫。除了像 BOINC 透過平行處理的技術來暫緩半導體計算機計算能力的不足，發展其它非傳統式計算機 (unconventional computer) 也將成為無可避免的趨勢，因為摩爾定律終將失效，而始終有電腦無法決解的問題需要被解決。