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秒。所以在设计与使用算法时，好的算法和不好的算法有着天壤之别。