1-2　不好的算法與好的算法

1-2-1　不好的算法

一個好的算法能在一秒內就得到答案，相同的問題用了一個不好的算法，可能計算機執行了上千億年也得不到答案。

假設一個數列有2個數，分別是1和2，這個數列的排序方式有下列2種。

假設一個數列有3個數，分別是1、2和3，這個數列的排序方式有下列6種。

上述可以列出所有排列的可能方法稱枚舉方法（Enumeration method），特色是如果有n個數，就會有n!種組合方式，如下所示。

2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6

上述n!又稱階乘數，階乘數概念是由法國數學家克里斯蒂安·克蘭普（Christian Kramp，1760—1826）所發表，他雖學醫但是卻同時對數學感興趣，發表了許多數學文章。

程序實例ch1_1.py：輸入n，程序可以列出它的階乘結果，這個程序相當于列出數列內含n個數的組合方式有多少種。

執行結果

注　在程序語言內部是使用棧（stack）處理遞歸式的調用，本書在1-4-2節與5-5節會一步一步拆解此程序有關棧內存的變化。

假設有一個數列內含30個數，則組合種數如下：

假設一個數列有30個數，分別是1～30，我們要將數列從小到大排列成1， 2， …，30。假設所使用的方法是枚舉方法，對所有的排列一個一個處理，如果不是從小排到大，則使用下一個數列，直到找到從小排到大的數列。由階乘得到的排列組合方式的種數，就是將數列數據從小排到大，最差狀況需要核對的次數。

注　枚舉方法的特色是一定可以找到答案。

程序實例ch1_2.py：延續前面概念，假設超級計算機每秒可以處理10兆個數列，運氣最差的話，請計算需要多少年可以得到從小排到大的數列。

執行結果

從上述執行結果可知，僅僅對含30個數的數列排序需要8411億年才可以得到結果，讀者可能覺得不可思議，筆者也覺得不可思議。一個程序，從宇宙誕生運行至今仍無法獲得解答。

1．宇宙誕生

2．銀河系誕生，距宇宙誕生約7億年

3．地球誕生，距宇宙誕生約90億年

4．現代，距宇宙誕生約137億年

Python有一個itertools模塊，此模塊內有permutations（ ）方法，這個方法可以枚舉列出元素所有可能的位置組合。

程序實例ch1_3.py：列出列表元素1、2、3所有可能的組合。

執行結果

1-2-2　好的算法

相同問題如果使用好的算法，可能不用1秒就可以得到答案。下列是筆者使用選擇排序法處理相同問題所需的時間。

第1循環是從n個數中找出最小值，放到新的數列內，此時需要確認n個數字。第2循環是從n-1個數中找出最小值，然后放到新的數列內，此時需要確認n-1個數字。第3循環是從n-2個數中找出最小值，然后放到新的數列內，此時需確認n-2個數字。最后執行n循環就可以產生新的從小排到大的數列。整個循環過程的數學概念表示如下：

n + (n-1) + (n-2) + … + 2 + 1

上述計算了所需確認的數字個數，也可以用下列方法表示：

從上述公式也可以得到下列結果：

假設這個數列有30個數，相當于n等于30，可以得到n2等于900，前一小節我們假設超級計算機每秒可以處理10兆（1013）個數列，故采用這種算法所需時間如下：

900 / 1013

結果遠遠低于1秒。所以在設計與使用算法時，好的算法和不好的算法有著天壤之別。