算法思维

​

什么是算法思维？

算法思维是一种习惯：把会重复的事，写成另一个人能够执行、也能够核对的有限流程。

给定两个彼此不互素的数，求它们的最大公度量。

这是希思（Thomas L. Heath）英译欧几里得《几何原本》第七卷命题 2 的任务，这里译成中文。原书没有使用 algorithm 这个词。“彼此不互素”对应的是后来教科书里的“不互素”。这条命题仍然点明了输入、动作的顺序，以及停止的地方。 日常的画面是贴在共用冰箱上的食谱卡。“看到合适了就停”要下一个人去猜。“小火十二分钟，然后停”不用猜。分析思维 说明问题的各部分怎样互相依赖。它本身并不把一个会停止的流程交给下一个人。演绎推理 问的是：前提为真时，结论是否必然跟着成立。本站的演绎推理页用《几何原本》谈的是那种链条。流程里的某一步可以是一次演绎。这里的习惯是整条流程，包括它在哪里停。 计算思维 是更大的一套。2011 年，ISTE 与计算机科学教师协会把算法思维放进那一套里，称作“一系列有序步骤”。本页就是这一系列。满意化思维 在选项跨过一条标准时停下来。那也是一条停止规则。它并不要求步骤明确到第二个人会走到同一个选项，并且能够核对。 一个人无法查看其步骤的机器学习模型，是另一件东西。高德纳的可执行性检验是铅笔和纸。下一个人做不了这一步，流程就还没写完。

​

算法思维的三层理解

• 入门：线索是一件你会重复的事。写下输入、按顺序排列的步骤，以及停止处。如果第二个人还得问你是什么意思，这一步就还不明确。
• 实践：让另一个人用一个普通例子和一个别扭的例子各跑一遍。两遍结果分叉的地方，就重写那一步。卡片上加一个代号，并不算完成这次核对。
• 进阶：在你要覆盖的例子上从不改变输出的那一步，核对之后可以删掉。一条可能永远不停的流程，在高德纳的意义上不是算法。某一群人身上很高的灵敏度，并不是一张许可证，不能把步骤用到推导时排除在外的人身上。

​

起源

把会停止的流程写下来，这个习惯比英文里的那个词更早。词本身、高德纳的五项特征，以及学校里的名称，都来得更晚。它们指的范围并不相同。 《几何原本》第七卷命题 2，求两个不互素的数的最大公度量。如果较小数能量尽较大数，它就是最大公度量。如果不能，就把较小数从较大数里一次次减去，直到剩下一个能量尽前一个数的数。命题 1 是相邻的情形。如果这个过程剩下一个单位，这两个数就互素。Britannica 把《几何原本》定在约公元前 300 年。那是这本书通常的年代，不是一份签了日期的手稿。命题用的是反复相减。后来的教学常常把一串减法换成一次除法的余数。这个捷径是等价的。它不是第七卷的措辞。高德纳把后来的形式叫做欧几里得算法。那个名字是他用来举例的算法。它不是欧几里得书里的词。 algorithm 这个词来自一个名字，不是来自欧几里得。穆罕默德·伊本·穆萨·花拉子米（al-Khwarizmi）九世纪在巴格达工作，在智慧宫，当时的哈里发是马蒙。Britannica 把两本书分开。《Al-Kitāb al-mukhtaṣar fī ḥisāb al-jabr waʾl-muqābala》是代数书。algebra 这个词来自书名。另一本讲印度数字计算的算术书，以拉丁文本留下来，题为 Algoritmi de numero Indorum（“花拉子米论印度算法”）。algorithm 来自这个标题里的拉丁化名字 Algoritmi。这本算术的阿拉伯文原本没有留存。MacTutor 数学史指出，已知拉丁文本改动很大，阿拉伯文原题也不为人知。本页不把他写成流程的发明者。第七卷更早。他是这个词的名字来源，也是系统计算的作者。 高德纳（Donald Knuth）在《The Art of Computer Programming》第 1 卷《Fundamental Algorithms》（Addison-Wesley，1968）第 1.1 节写下五项特征。有限：流程在有限步之后停止。明确：每一步把动作规定到每一种情形都没有歧义。输入：零个或多个量，取自写明的集合。输出：一个或多个量，与输入有写明的关系。可执行：每个操作都基本到一个人用铅笔和纸，可以在有限时间里精确做完。在那一节里，一条可能永远不停的流程是 computational method，不是算法。他是在命名特征。他不是在报告这个习惯的一次试验。 Gerald Futschek 2006 年在维也纳工业大学写了学校里的这个名称。章节收在《Lecture Notes in Computer Science》第 4226 卷，第 159–168 页。他说这个词当时已经常被用来指信息学教育里的一种能力。他没有把自己写成造词的人。他描述的是一组能力：分析问题并把它写精确；找到合适的基本动作，并用这些动作造出正确的算法；把特殊情形和通常情形都想过，然后再提高效率。他认为这些能力可以在不学编程的情况下培养。那门大学预科课里的图，是为了让正确性、终止、效率、确定性与并行变得看得见。那是一门课的教学目标。它们不是一项测到的增益。 2011 年，国际教育技术协会（ISTE）与计算机科学教师协会发表了一份面向 K–12 的计算思维操作定义。他们报告说，近 700 名计算机科学教师、研究者和实践者接受了调查，并且压倒性地支持这份文本。清单上的一行是：“通过算法思维把解法自动化（一系列有序步骤）。”定义说，计算思维包括这份清单，并且不限于它。在本站，计算思维是更大的一套。算法思维是那套有序的流程。

​

核心要点

当一个当时不在场的人可能得把这件事再做一遍时，算法思维用得上。某一步仍然要靠你私下的判断，或者流程没有停止处，它就会停住。

​

应用场景

当别人可能重复这件事，而你需要一个能够核对的结果时，使用算法思维。写下输入、明确的步骤和停止处。然后让第二个人试那个别扭的例子。

​

经典案例

渥太华踝关节规则（Ottawa ankle rules）是为一个急诊决定写下的流程。这个成年人、这次踝关节急性受伤，需不需要拍片？Ian Stiell 与渥太华的同事写出规则，然后试验其他医师被要求使用它们时发生了什么。这些试验测量的是急诊部门里的这次引入。它们不测量厨房、教室，或一个下午对着空白卡片养成的习惯。 Stiell 与同事在 1993 年 3 月 3 日的《JAMA》（第 269 卷，第 1127–1132 页）报告了精炼后的规则。只有踝区有疼痛，并且下列三项里至少有一项，才做踝部 X 线系列。一项是腓骨后缘远端 6 cm 或外踝尖的骨压痛。另一项是胫骨上同样的压痛，沿后缘或在内踝尖。第三项是受伤当时和在急诊部门都不能负重走四步。足部系列改用中足区。第五跖骨基底骨压痛、舟骨骨压痛，或同样的四步失败，才做足部系列。四步是指每条腿各转移两次体重。跛行也算。论文说，先判断骨压痛，再让人走，并且绝不强迫。 那次精炼排除了好几组人。它排除 18 岁以下、妊娠，以及单纯的皮肤损伤。它也排除已经带着片子转来的人、受伤超过 10 天，以及同一次受伤的复诊。论文说，更早的一条年龄标准，以及一条骰骨压痛标准，是多余的。那次精炼里有临床意义的骨折，没有它们也能识别出来。 同一篇论文有两个阶段，结果不是同一个。第一阶段，原始规则对 121 例踝区骨折的灵敏度是 1.0，95% 置信区间从 0.97 到 1.0。对 49 例中足区骨折，灵敏度是 0.98，区间从 0.88 到 1.0。116 名患者上对规则的解读仍在第一阶段，踝部系列的 kappa 是 0.56，足部系列是 0.69。两位读者并不总是标出同一个结果。这不是后来医院里精炼规则的一致程度。第二阶段，精炼后的规则对 50 例踝区骨折的灵敏度是 1.0，区间从 0.93 到 1.0。对 19 例中足区骨折，灵敏度也是 1.0，区间从 0.83 到 1.0。论文的结论把精炼后的规则称为 100% 灵敏。这个说法跟着的是 1.0 的点估计。区间比一个单点更宽。论文还估计，踝部系列的拍片有可能减少 34%，足部系列有可能减少 30%。如果规则为阴性，它把骨折概率估计为 0%。踝部系列的区间从 0% 到 0.8%，足部系列从 0% 到 0.4%。这 34% 和 30% 是验证样本里的潜在降幅。它们不是后来试验的结果。 1994 年 3 月 16 日的《JAMA》（第 271 卷，第 827–832 页）把规则带进两家医院。设计不是随机的。它使用前后两个时期，以及一家同期的对照医院。前后各五个月里，共有 2,342 名踝关节急性受伤的成年人。实施医院的踝部拍片相对减少 28%，对照医院增加 2%。实施医院的足部拍片相对减少 14%，对照医院增加 13%。在实施医院的后一时期，没有骨折的患者里，未拍片就离开的人在科室待了 80 分钟，拍了片的人待了 116 分钟。论文估计的医疗总费用，含医师诊视和拍片，是 $62 对$173。对急诊医师照护的满意度是 95% 对 96%。这两组后来再拍片的比例都是 5%。74 例踝部骨折的灵敏度是 1.0（区间 0.95 到 1.0），19 例中足骨折也是 1.0（区间 0.82 到 1.0）。随后 12 个月，实施医院的拍片用量没有回升。分钟之差和金额之差比较的是后一时期里的两组人。它们不是整个科室的前后对比。论文没有写明这些金额用的是哪一种货币。 范围更大的试验是 Stiell、George Wells、Andreas Laupacis 与同事，发表于 1995 年 9 月 2 日的《BMJ》（第 311 卷，第 594 页）。这是一项多中心的前后比较试验，在加拿大八家教学医院和社区医院的急诊部门进行。这些社区的人口从 1 万到 300 万。全部 12,777 名踝关节急性受伤的成年人都包括在内：对照期 6,288 人，实施期 6,489 人。对照期是 1991 年 5 月 1 日到 1992 年 4 月 30 日。实施期是 1993 年 1 月 1 日到 12 月 31 日。两个时期不是紧挨着的连续两年。200 多名医师通过一小时讲课学习规则，另有讲义、口袋卡片，以及每个科室两张海报。某一个患者拍不拍片，仍由接诊医师决定。分析保留每一名合格患者，不论那位医师有没有填表，也不论有没有遵守规则。论文把有临床重要性的骨折定义为宽度大于 3 mm。 对照期有 82.8% 的患者接受踝部拍片（6,288 人中的 5,207 人），实施期是 60.9%（6,489 人中的 3,955 人）。论文把这个变化称为相对减少 26.4%，P 小于 0.001。这一比例在全部八家医院都下降，也在预先划定的亚组里下降：社区医院、教学医院、急诊医师、家庭医生和住院医师。足部拍片并没有一起动。三家医院有显著减少。五家没有显著变化。实施期里，完全没有拍片的患者更多（21.7% 对 8.4%），踝部与足部两个系列都拍的更少（9.2% 对 21.8%）。 时间和账单是实施期内部的比较。它们不是科室的前后对比。没有骨折、也没有拍片的患者，在科室的平均时间是 54.0 分钟，标准差 42.0。拍了片的人是 86.9 分钟，标准差 46.9。电话随访到的患者，平均总费用是 70.20 美元（标准差 52.1）对 161.60 美元（标准差 71.2），按 1993 年美元计算。这些费用覆盖的是这一随访子集的急诊与复诊，以及 X 线系列。它们不是一个卫生系统被测到的节省。作者的结论说，这次引入带来了更短的等待和更低的费用。印出来的比较并没有给出科室平均等待时间或预算在前后的数字。 漏诊骨折也要用同样的方式看待分母。论文说，对照期没有漏诊骨折的数据。实施期的随访里，2,033 人中有 10 人出院后被诊断出骨折，且没有新的受伤。拍过片的 732 人里有 3 人在这 10 人之中（0.4%）。没有拍片的 1,301 人里有 7 人在这 10 人之中（0.5%）。摘要里的“0.5 对 0.4”就是这个比较。它不是对照期比率对实施期比率。结果部分说，这 7 人里只有 1 人是正确应用了规则。讨论部分指向同一张表，说未拍片这一组的漏诊来自没有使用规则或读错了规则，另有 1 例来自明显肿胀。全部 10 人在六个月时都已愈合，没有延迟，也没有长期影响。没有人提起诉讼。另一个计数发生在出院之前：1,090 例重要骨折里有 6 例，规则被读成阴性。这 6 例里，医师出于别的理由开了片子，主要是明显肿胀。阴性解读在这 6 例里不是最后一句。 论文还印了两个相邻的人数，本页不把它们合成一个。它说电话样本 2,171 人中联系上了 2,032 人（93.6%）。骨折那一句用的分母是 2,033。两个数字都是论文里的。它们不是一个四舍五入后的计数。 表格方面，医师为 6,489 名实施期患者中的 77.1% 填了研究表（5,003 人）。论文接着报告，踝部病例的准确解读是 97.1%，足部是 97.6%；踝部的满意依从是 95.3%，足部是 95.0%。那一句没有再次写明分母。规则判定为不必要的拍片仍然发生在 4.9% 的病例里，其中 0.5% 是因为患者坚持。医师说自己在 3.8% 的病例里对使用规则感到不安。讨论点名了常见的读法错误：忽略内踝压痛，或者没有把腓骨后缘远端 6 cm 全部触诊到。有些骨折在尖端上方 5 或 6 cm 处穿出骨质。 Bachmann 与同事在 2003 年 2 月 22 日的《BMJ》（第 326 卷，第 417 页）综述了同一套规则。他们纳入 32 项研究，元分析使用其中报告了 15,581 名患者的 27 项。合并后的阴性似然比，踝部是 0.08（区间 0.03 到 0.18），中足是 0.08（0.03 到 0.20）。儿童的两个部位合并后是 0.07（0.03 到 0.18）。综述说灵敏度几乎是 100%，特异度不高，使用后应当把不必要的拍片减少 30% 到 40%。综述内部，报告的灵敏度从伤后 48 小时内应用规则的研究中的 99.6%，到合并评估研究中的 96.4%。“应当减少”是综述对使用效果的结论。它不是 1995 年试验里 26.4% 的相对减少，也不是 1994 年那家医院 28% 的相对减少。统计思维 要让点估计、区间、相对减少和似然比不要塌成一个数字。 教训很窄。一套写下了部位、数得清的行走和停止处的流程，可以教给没有参与撰写的医师。在这些试验里，踝部拍片下降了。1995 年的论文并没有显示，未拍片回家的人后来骨折的比率高于拍了片的人。同一份记录也显示流程的限度。1993 年读者并不总是一致。1995 年八家医院里有五家的足部片子没有下降。6 例重要骨折出现在卡片被读成阴性的时候。1 例后来的骨折跟在一次正确的“不拍片”之后。系统思维 还会把卡片外面的东西算进去：那一小时的教学、海报，以及医师仍然可以下令拍片。这些试验没有给出这个习惯在一般情况下的效应。

​

边界与失效场景

算法思维在三处失效。任务可能没有能够核对的输出。步骤可能被用到它们所写明的输入之外。或者某项研究的百分比被当成了这个习惯本身的属性。 第一条边界是稳不住的任务。第七卷假定两个数和一种量尽。踝关节规则假定一次在名单之内的急性受伤。第一次谈话、一场道德冲突，或者一个对不上输入的案例，都还没有流程。为了让卡片存在而写下步骤，并不会造出一个能够核对的输出。计算思维仍可以帮助你把一团乱分开。这个习惯从你能够写下输入和停止处的时候开始。 第二条边界是规则留在外面的人。1993 年的精炼排除了儿童、妊娠、单纯皮肤损伤、别处已经拍过的片子、超过十天的受伤，以及复诊。1995 年的试验纳入的是成年人。它的讨论另列了一张单子，作者说这些情况下评估可能不可靠：意识改变、醉酒、另有疼痛的损伤、腿部感觉减退，或语言障碍。它也提到明显肿胀会让后缘无法触诊。Bachmann 的综述把一个儿童亚组合在一起，阴性似然比是 0.07。那一行说的是进入汇总的那些研究里的规则。它不是一项发现，说成人卡片可以不经另一次核对就抄到每一个孩子身上。流程只在它写明的输入之内才是明确的。 常见的误用，是把百分比当成这个习惯的证明。不要把 26.4%、28%、34% 或 30% 引成算法思维、一次工作坊或一张家庭卡片的效应。1993 年的数字是验证样本里的潜在降幅。1994 年的数字是相对一家同期医院的相对变化，设计并非随机。1995 年的数字是两个隔开的年份之间的相对变化，发生在讲课和海报之后，医师仍然可以自由下令拍片。不要把 54 分钟对 87 分钟，或 70.20 美元对 161.60 美元，引成一个科室的前后对比。那些差距在实施期内部，比较的是没有骨折的患者里拍了片和没拍片的人。不要把讨论里约成“大约 90 美元”的差距，或它说这八家医院若减少 25% 就会节省可观费用的那句话，当成另一次测量。不要把 1.0 的灵敏度引成保证。1993 年第一阶段对 49 例中足骨折是 0.98。1994 年中足的区间在 19 例骨折上从 0.82 到 1.0。Bachmann 的合并评估数字是 96.4%。不要把综述的 30% 到 40% 引成那些试验测到的降幅。

​

常见误区

有三种混淆会跟着这个名字走。这个习惯会被误认为编程，被误认为那套更宽的计算思维，也被误认为一条灵敏的规则走到哪里都成立。

​

相关概念

算法思维旁边，是把事物拆开、推出必然结论，或因别的理由停下来的习惯。下面的链接是邻居。它们不是这套流程的别名。

​

一句话总结