算法就是一步一步的做法,跟有没有电脑没关系。 十张牌找最大:拿第一张当擂主,后面比它大就换人,比完就是答案。 电脑和人做的事一模一样,差别只在快慢。
第 0 章不存在这一篇,这是全书的第一篇。所以这里不假设你写过代码。 教材用「算法其实就在身边」开篇,想把「算法」这个词从神坛上拿下来。 这一篇也只讲一件事:算法是做法,不是程序。
一、先看一件天天做的事
从十张摊开的牌里找出最大的一张,人会怎么做? 拿起第一张,先当成最大的。看下一张,比手里的大就换成它。还有牌就继续,没牌了,手里那张就是最大的。 这四句话就是算法。它没有提到电脑,也没有用到数学。
教材把这一条放在最前面,是因为「算法」这两个字听起来太唬人。 其实它就是「把一件事拆成能照着做的几步」。 做菜有菜谱,装柜子有说明书,组装玩具盒里有图纸——那些都是算法。
二、把它写成代码,一个字都没变
演示里那四步原样翻成了代码:先 best = cards[0],再一个循环加一个 if,循环走完就结束。
每一行代码都能对回一句话。没有多出来的步骤,也没有藏起来的技巧。
这就说明一件事:写代码不是另起一件事,是把已经想清楚的步骤换一种写法。
反过来说,想不清楚的步骤写不成代码。卡住的时候,多半不是语法不会,是那一步还没想明白。 所以学算法的顺序是:先说清怎么做,再想怎么写。跳过第一步,写出来的东西自己都不敢改。
三、电脑的优势只有一条:快
演示里十张牌比了九次。一百张就九十九次,一千张就九百九十九次。 人做这件事,几十张就开始烦;电脑做一千万张也就是一两秒。 所以电脑没有比人聪明,它只是不会累、不会烦、不会看漏。
这句话听起来像常识,但它决定了很多事:为什么算法要研究「数据变多时涨得多快」——因为在电脑上, 唯一值钱的就是这个「快」。 也解释了另一件事:同样的算法,人做和电脑做结果一样,只是速度差几个数量级。 这也是为什么算法可以先在纸上推演,再上机验证。
四、这一篇要带走的东西
三句话:算法是步骤,不是程序;步骤清楚才能写成代码;电脑只贡献速度。 下一节讲「什么样的步骤才算算法」——光有步骤不够,还得满足两个条件。 那两条条件看着像文字游戏,其实决定了你写出来的循环会不会卡死。
五、动手 Demo:十张牌找最大:四步、九次比较
把「找最大」这件事拆成四步,再原样写成代码。 然后拿人去对照一遍,看两边是不是同一件事。 最后看数据变多时,比较次数怎么涨。
cards = [7, 2, 9, 4, 11, 5, 8, 1, 6, 3]
best = cards[0] # 1. 拿起第一张当擂主
for x in cards[1:]: # 2. 看下一张
if x > best: # 比它大就换人
best = x
# 3. 没牌就停(循环自己结束)
print(best) # 4. 手里这张就是最大的
实跑输出:
--------------------------------------------------------------------
算法就在身边:十张牌找最大
--------------------------------------------------------------------
① 一件事拆成四步
--------------------------------------------------------------------
要从十张牌里找出最大的一张,人会这么做:
1. 拿起第一张,先当成最大的
2. 看下一张,比手里的大就换成它
3. 还有牌就回到第 2 步
4. 没牌可看了,手里那张就是最大的
这四行就是算法:一步一步、每步都清楚、走完会停。一个字都没提电脑。
② 把这四步原样写成代码
--------------------------------------------------------------------
cards = [7, 2, 9, 4, 11, 5, 8, 1, 6, 3]
最大的那张:11
一共比了 9 次(10 张牌,比 n-1 次)
每一行代码都能对回上面那一步:best = cards[0] 是第 1 步,for 加 if 是第 2、3 步,
循环结束是第 4 步。
③ 人做一遍,电脑做一遍
--------------------------------------------------------------------
| 步骤 | 人怎么做 | 电脑怎么做 |
|---|---|---|
| 1 拿第一张 | 手拿起最上面那张 | best = cards[0] |
| 2 比一比 | 眼睛看,心里比 | if x > best |
| 3 重复 | 翻下一张 | for x in cards[1:] |
| 4 停下 | 没牌了就停 | 循环自然结束 |
四步一模一样。差别只有一个:人翻十张要几秒,电脑翻一千万张也是几秒。
这就是学算法时最该记住的第一句:算法是人想出来的,电脑只负责跑得快。
④ 为什么值得拿十张牌说事
--------------------------------------------------------------------
| 牌的张数 | 比较次数 | 倍数 |
|---:|---:|---:|
| 10 | 9 | 1 |
| 100 | 99 | 11 |
| 1000 | 999 | 111 |
| 10000 | 9999 | 1111 |
牌多十倍,比较次数也多十倍——这叫「线性」。写得再漂亮也逃不掉,因为每张牌至少要看一眼。
所以评价一个算法快不快,看的不是它跑了几毫秒,是「数据变多时它涨得多快」。
①第一段那四行是「人话版」的算法。注意它一句都没提电脑。 ②第二段输出「最大的那张:11」和「比了 9 次」。十张牌比九次,不是十次——第一张不用跟自己比。 ③第三张表把人和电脑并排。四步一一对应,说明写代码只是换个写法。 ④最后那张表是这一篇的重点:牌多十倍,比较次数也多十倍。 这就是「线性」的样子,后面第 5 章、第 6 章都在比这个涨法。
30 秒实验
- 把十张牌换成一副五十四张,算一下最多比几次。
- 改一行,让它在找最大值的同时把最小值也找出来,看要多比几次。
- 想一个「不用每张都看」也能找出最大的办法——想不出来就说明为什么必须每张都看。
常见误区
- 「算法是程序员才学的东西。」做菜、找路、排队都在用算法,只是没人给它们起这个名字。
- 「算法等于程序。」程序是算法的某一种写法。同一个算法,可以用任何语言写。
- 「电脑比人聪明所以找得快。」它只是不累。步骤还是人想出来的。
自测三问(点开对答案)
1. 算法和程序的区别是什么? —— 算法是步骤本身,程序是步骤的某一种写法。同一套步骤可以写成任何语言的程序。 2. 十张牌找最大,为什么比九次不是十次? —— 第一张直接当擂主,不用跟自己比。n 个数据找最大,比 n-1 次。 3. 牌从十张变成一百张,比较次数怎么变? —— 从九次变成九十九次,也是十倍。这叫线性增长。只有步骤还不算算法。下一节补上两个必须满足的条件,其中一个直接决定你的循环会不会卡死。
- ☐ (本篇完,下一篇 1.2 好算法的两个条件)