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，可以得到n ² 等于900，前一小节我们假设超级计算机每秒可以处理10兆（10 ¹³ ）个数列，故采用这种算法所需时间如下：

     900 / 1013

结果远远低于1秒。所以在设计与使用算法时，好的算法和不好的算法有着天壤之别。 ECsf1batlj0LsNbVzESpl2c/KEVTBGjEP4p5PPBth2o7qMWw7FwR1W6/31YiCIaZ