波仔
🧮 第1章 什么是算法
📄 一句话概括

两个条件：能停下来、每一步没歧义。缺一个就不算算法。 「加适量的盐」在纸上能过，在代码里过不去——电脑不会替你猜。 满足这两条只是及格。及格之上还有一条：数据变大时涨得快不快。

📝 本章和前面几章的关系

上一篇讲了「算法是步骤」。这一篇讲「什么样的步骤才算数」。 教材把这两条叫「有穷性」和「确定性」。名字唬人，意思很朴素。 这一篇还会顺带说明一件事：能跑通和有价值，是两回事。

一、条件一：能停下来

演示里写了一句 while True: n += 1，跑 0.05 秒就数到十六万多，还在数。 每一步都对，做的事也清楚，但它不停，所以它不是算法。 教材把这一条叫有穷性：步骤必须有限，走完必须结束。

这一条不是文字游戏。 写循环时忘了改条件变量、改了但方向反了、条件永远成立——这三种错每天都在发生， 结果都是程序卡在那里不动。 判断办法很简单：问自己「这个循环靠什么退出」。答不上来，就是写错了。

二、条件二：每一步没歧义

「加适量的盐」「看情况处理」「把大的放前面」——这三句话在纸上都通，在代码里两通一不通。 演示里拿 None + 1 试了一下，直接 TypeError。含糊的话在代码里过不去。 所以「确定性」这一条不是挑剔，是写法逼出来的：电脑不会替你猜，它只会照字面执行。

写需求、写注释、给同事讲方案，这一条同样成立。 「优化一下性能」不是需求，「把首页加载从 3 秒压到 1 秒内」才是。 这也解释了一个常见现象：跟电脑说不清的事，往往跟人也说不清。能被写成代码的描述， 本身就是想清楚了的标志。

三、两条都满足，也不一定是好算法

演示里算了 1 到一千万的和，两种写法：循环加一千万次，或者套公式一次算完。 两个结果一样，都满足能停、没歧义。但一个要一秒多，一个快到测不出来。 所以那两个条件是底线，不是全部。底线之上还有一条：数据变大时，它涨得多快。

这句话是全书的骨架。 后面第 4 章数循环次数、第 5 章比排序的步数、第 6 章比查找的次数，比的都是这一件事。 顺带一句：公式法之所以快，是因为它把「重复」换成了「推导」。 能推出公式的场合，就别用循环——这是算法思维最实用的一条。

四、演示里那个刹车

演示 ① 里我加了一句「跑满 0.05 秒就停」。那不是算法的一部分，是演示的保险。 没有这根刹车，这个 Demo 会一直跑到你按 Ctrl+C。这正好说明「停不下来」有多麻烦。 真实系统里也有类似的保险：接口超时、任务超时、循环上限。它们的名字都叫「防止无限」。

所以「能停下来」这一条，工程上是要靠代码兜的，不能只靠想清楚。

五、动手 Demo：两个条件：让它停不下来、让它含糊、再让它变快

先写一句永远不停的循环，看它 0.05 秒能跑多少。 再把一句含糊的话写进代码，看电脑怎么回。 最后用两种办法算同一个和，比一次耗时。

# 1 停不下来：每一步都对，但它不是算法
n = 0
while True:
    n += 1                # 靠什么退出？没有答案

# 2 含糊：纸上能过，代码过不去
None + 1                  # TypeError: 电脑不会替你猜

# 3 都能停、都没歧义，但一个慢得多
s = 0
for i in range(10000000): s += i      # 一千万次
n * (n - 1) // 2                      # 一次

实跑输出：

--------------------------------------------------------------------
好算法的两个条件：能停、没歧义
--------------------------------------------------------------------


  ① 条件一：能停下来
  --------------------------------------------------------------------
  while True: n += 1  这一句跑了 0.05 秒
  已经数到 167985，仍然没有停下来的迹象
  这段代码每一步都对，做的事也清楚，但它不是算法——因为它不停。
  教材把这一条叫「有穷性」：步骤必须有限，走完必须结束。
  ! 注意这里的 0.05 秒是我硬加的一根刹车。没有这根刹车，这个 Demo 就跑不完了。

  ② 条件二：每一步都没有歧义
  --------------------------------------------------------------------

| 说法 | 能不能写成代码 | 问题在哪 |
|---|---|---|
| 加适量的盐 | 不能 | 适量是多少，没说 |
| 把大的放前面 | 能 | 大的定义清楚 |
| 看情况处理 | 不能 | 什么情况、怎么处理都没说 |
| 取余数 | 能 | 除不尽剩下的那部分 |

  试着把一句含糊的话写进代码：
  None + 1  ->  TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'
  含糊的话在纸上能过，在代码里过不去。
  所以「确定性」这一条不是挑剔，是写法逼出来的：电脑不会替你猜。

  ③ 能停、没歧义，但还是很慢
  --------------------------------------------------------------------

| 算法 | 做法 | 1 到 10000000 求和 | 最快耗时 |
|---|---|---|---|
| 逐个加 | 循环加 10000000 次 | 49999995000000 | 1189.92 毫秒 |
| 套公式 | n(n-1)/2 一次算完 | 49999995000000 | 0.0004 毫秒 |

  两个结果一样（49999995000000），都满足「能停、没歧义」，但一个要 1190 毫秒，一个快到测不出来。
  所以「好算法」的两个条件是底线，不是全部。底线之上还有一条：数据变大时，它涨得慢不慢。
  这里的耗时是本机实测（每个跑多轮取最快），换台电脑数字会变，但「一个毫秒级、
  一个微秒级」这个量级差不会变。

①第一段里那个十六万多的数字，是这 0.05 秒真跑出来的。 换台机器数字会变，但「跑了十几万次还没停」这个事实不变。 ②第二张表四行，第三行「把大的放前面」能写成代码——因为「大」有明确含义。这就是确定性的分界线。 ③第三段那个 TypeError 是原文照抄的报错，不是编的。 ④最后那张表两个结果一样（49999995000000），一个一千多毫秒，一个 0.0004 毫秒。量级差了一百万倍。 ⑤注意那句「每个跑多轮取最快」——计时必须这么测，不然会把启动开销算进去。

30 秒实验

  1. 把 while True 改成 while n < 10，看它能不能停，停在第几。
  2. 把 n * (n - 1) // 2 换成 n * (n + 1) // 2，看结果变成多少、哪个才对。
  3. 想三句你自己的工作里「说得很含糊」的话，把它们改成能验证的说法。

常见误区

  1. 「只要能算出来就是算法。」停不下来的不算。看看你的循环靠什么退出。
  2. 「含糊一点没关系，人听得懂。」电脑听不懂。能被写成代码，才说明想清楚了。
  3. 「满足两个条件就是好算法。」那是及格线。及格之上还要看数据变大时涨得多快。
自测三问（点开对答案） 1. 两个必要条件分别是什么？ —— 有穷性（能停下来）和确定性（每一步没歧义）。缺一个就不算算法。 2. 怎么快速判断一个循环会不会停？ —— 问「它靠什么退出」。答不上来就是会死循环。 3. 为什么说「能跑通」不等于「好算法」？ —— 能跑通只是满足了底线。同样能跑通的两个写法，数据一大可能差一百万倍。

两个条件管的是「对不对」。下一节讲「怎么写才不容易错」——答案是只用三块积木，不加第四块。

相关笔记