我教孩子学算法

寒假到了，如何让孩子过得更加充实？正好自己前两天看一本算法书，挑前面几个简单的算法给孩子讲讲，也算是给孩子做个启蒙。为了帮助他更好地理解，做了段程序演示下。顺序普及下Python代码。

1. 起步：数据查找

人生基本上就是两件事，选题和解题。最好的人生是在每个关键点上，既选对题，又解好题。人生最大的痛苦在于解对了题，但选错了题，而且还不知道自己选错了题。正如人生最大的遗憾就是，不是你不行，而是你本可以。

作为开始的起步，从简单的找数开始。如何从一组有序的数字集合中，找到指定的数字。这其中有两个经典的算法：顺序查找和折半查找（也叫做二分查找）。

❖ 顺序查找

顺序查找，顾名思义就是在数据集合中一个一个查找，如何找到指定的数字返回就可以了。用Python实现起来，就是简单的循环即可。

❖ 折半查找

折半查找，相对复杂一些，就是在集合中寻找时，取其中点位置，进行比较。如果目标数大，则在右半区（大的区间）寻找；反之则在小的区间寻找。

❖ 对比：两种查找方法

孩子在学习这部分，是比较枯燥的，特做了个图形化展示。模拟一个集合（1..100），测试100次，每次取1~100中的随机数进行查找比较。为了比较两者的运算速度，将不同算法执行时的比较次数抽取出来，做了对比图看看。

如上图，在100次对比测试中，蓝色圆形代表的折半查找，其查找的次数总是很平均，大致在0~10这个区间中；而代表顺序查找的桔色方形，则偏差很大。尽管个别情况下，出现顺序查找的比较次数较少，但大多数情况下还是折半查找的比较次数少。为了便于说明，还做了个统计图。

为了更形象的对比，这里引入了箱式图，做了个统计图。（顺便普及下统计学，呵呵）。在折半查找中，其比较次数的范围在3~7之间，中位数在6。简单理解，就是平均比较6次就能得到结果。而使用顺序查找的方式，比较次数的范围则在1~98，中位数在54，也就是说平均要比较接近一半(100/2=50)，才能找到目标值。

2. 进阶：数据排序

人生基本上就是两件事，选题和解题。最好的人生是在每个关键点上，既选对题，又解好题。人生最大的痛苦在于解对了题，但选错了题，而且还不知道自己选错了题。正如人生最大的遗憾就是，不是你不行，而是你本可以。

上面谈到的集合，都是数字排序的，那么如何对数字进行排序呢？这里可以采用两种常见的方式：选择排序和快排序。

❖ 选择排序

选择排序的基本原理，就是循环找出最小的。然后再次循环，找下一轮。简单说来就是两层循环比较。简单算法实现如下：

❖ 快排序

快排序则稍微复杂点，其用到了递归的概念。在比较数据时，将结合分为两个部分，大于和小于集合，然后再递归调用快排序算法，分别进行排序。以此往复，不断迭代。

❖ 对比：两种排序方法

针对这两种算法，可对比下其执行时长。这里通过对比不同数量级下，执行排序的时长加以说明。下图是对10、·100、1000、10000个随机数，使用不同算法的比较，单位是微秒。从中可以看出快排序要明显快于选择排序。

3. 延伸：衡量算法效率-大O法

人生基本上就是两件事，选题和解题。最好的人生是在每个关键点上，既选对题，又解好题。人生最大的痛苦在于解对了题，但选错了题，而且还不知道自己选错了题。正如人生最大的遗憾就是，不是你不行，而是你本可以。

如上面两类算法比较可见，不同算法的执行效率差别很大，那么如何比较不同算法的执行时长呢？这里引入了一个方法—大O表示法。它并不是以秒为单位的速度比较，而是通过比较操作数，衡量出算法运行时间的增速。借用书中的原图，表示常见的几个算法的执行效率。

下面按从快到慢的顺序列出了经常会遇到的5种大O运行时间

• O(log n) 也叫对数时间，这样的算法包括折半查找。
• O(n) 也叫线性时间，这样的算法包括简单查找。
• O(n＊log n) 这样的算法包括快排序，一种速度较快的排序算法。
• O(n2) 这样的算法包括选择排序，一种速度较慢的排序算法。
• O(n! ) 例子中未谈到的算法，比如旅行路径问题。