yh.
算法小课堂 / 第一讲

公司内部兴趣分享

ChatGPT 是不是一个算法？

算法小课堂 · 第一讲

先从每天用的产品出发，
再把一个小算法彻底讲清楚。

Pascal / 胡永祎
2026 年 9 月 10 日

讲解提示

先让大家凭直觉回答，不急着判对错。后面再回来：每个人说的 ChatGPT，可能根本不是同一个对象。

先建立直觉

竖式计算，也是一种算法

小学学过的乘法竖式，已经在规定“怎么算”。

  1. 从个位开始乘。
  2. 超过十就进位。
  3. 继续处理下一位。

例如 23 × 4

3 × 4 = 12
2 × 4 + 1 = 9

个位写 2，向十位进 1。
十位得到 9，结果是 92。

Algorithm 一词来自 9 世纪数学家 al-Khwārizmī 名字的拉丁化形式，与算术规则的传播有关。[1]

讲解提示

这一页只建立直觉：算法早于计算机。词源点到为止，不展开书名与版本考据。名字与花剌子模地区有关；不要把 al 单独解释为“来自”。

什么是算法

解决一类问题的明确步骤

为解决一类问题，
规定一套明确、可执行的步骤。

先用这句话理解“算法”。再用具体问题，检查这些步骤说清楚了没有。[1]

输入什么输出什么步骤明确吗能执行吗会结束吗

这一讲先讨论需要在有限步内结束的计算任务。随机选择也可以遵循明确的规则。[2]

讲解提示

五个问题是检查工具。这里强调的是更抽象的“问题与步骤”，不必让大家背定义。等 gcd 讲完，再回到这句话。

拆开开场问题

先说清楚：你指的是哪一部分？

作为产品

对话界面、文件、账户，以及用户怎样使用它。

作为系统

组织上下文，调用模型，执行工具，处理结果。

作为模型与计算

架构与参数，以及矩阵运算、注意力、采样等过程。

一个产品里，包含许多可以分别讨论的算法。

讲解提示

这些是讨论对象的不同范围，不是当前 ChatGPT 的内部架构图，也不是互斥分类。不要用“像不像算法”判断。界面可以承载或表达算法，图形编程也是表达方式；需要说明的是它具体在解决什么问题、执行什么步骤。

再按计算过程拆开

训练与推理，都包含算法

训练：得到模型参数

  1. 准备、筛选和处理数据
  2. 用当前参数计算预测与损失
  3. 计算梯度，更新参数
  4. 按训练安排继续迭代

数据处理、优化过程，都有各自的算法。

推理：使用模型参数

  1. 输入已有的 token
  2. 计算下一个 token 的概率分布
  3. 按规则选择或采样一个 token
  4. 加入上下文，继续生成

通常不更新权重；遇到结束条件或输出上限时停止。

算法可以出现在流程的不同环节。

以常见自回归语言模型为例；token 是文本片段，不一定是完整的词。训练目标和后训练方法还可以不同。[3][4]

讲解提示

训练与推理的拆法，和上一页不是同一条分类轴。强调：训练有训练算法，推理有推理算法，采样又是其中一个算法。先建立这个认识，今天不展开 LLM 的实现。

用一个小问题研究算法

最大公约数：一个说得清的问题

输入两个正整数 a、b，找出能同时整除它们的最大正整数。

26 的正因数1，2，13，26

6 的正因数1，2，3，6

共同的正因数1，2

gcd(26, 6) = 2

GCD = Greatest Common Divisor。2 整除 26，意思是 26 = 2 × 13。

讲解提示

先让大家说出 2，再引入 GCD 缩写。注意整除的方向：公约数 d 整除 a 与 b，也就是 a、b 都是 d 的整数倍。

先定义问题

定义了答案，还要确认它存在

gcd(a, b) = max { d ∈ ℤ>0 : d ∣ a 且 d ∣ b }

候选集合非空

1 总能整除 a 和 b。

所以至少有一个正公约数。

候选集合有限

d ≤ min(a, b)

公约数不会超过较小的那个正整数。

非空的有限集合，一定有最大元素。

讲解提示

讲清“存在性”这一层。定义告诉我们要什么，算法接下来回答怎么得到它。递归中会出现 0，后面单独解释 gcd(a,0)。

先认识接下来要用的运算

取模，就是取余数

26 里面有 4 个 6，还剩 2。

26 = 4 × 6 + 2
26 mod 6 = 2Python：26 % 6 == 2

一般写成 a = qb + r，其中 0 ≤ r < b，b > 0。

15 = 2 × 6 + 3，那么 15 mod 6 是多少？

讲解提示

停下来等答案 3，确认大家理解余数再翻页。区分商 2 与余数 3。不要默认大家记得 mod。

欧几里得算法

把一对数，换成更小的一对数

只要 b 还不是 0，就把

(a, b)
换成
(b, a mod b)

(26, 6)26 = 4 × 6 + 2

(6, 2)6 = 3 × 2 + 0

(2, 0)第二个数为 0，返回 2

gcd(a, 0) = a（a > 0）：每个正整数都整除 0，最大共同因数就是 a。
这是欧几里得算法的现代取余写法，古代文献已记录相关过程。[5]

讲解提示

把例子走完。这时只说“这是我们打算执行的步骤”，还没有证明它对。下一页强调表达方式，再分别问为什么答案不变、为什么能结束。

算法与表达方式

同一个算法，可以有不同的表达

自然语言

反复用“第二个数和余数”替换原来的两个数。第二个数变成 0 时，留下的非零数就是答案。

数学表达

gcd(a, 0) = a
gcd(a, b) = gcd(b, a mod b)

第二式要求 b > 0。

伪代码

GCD(a, b):
    while b ≠ 0:
        (a, b) ← (b, a mod b)
    return a

同时赋值：右边都使用更新前的 a、b。

也可以写成 Python、C，或图形化程序。

表达方式在变，背后的计算步骤没有变。

讲解提示

强调：算法比它的表达形式更抽象。自然语言方便交流，公式方便证明，伪代码更贴近实现。口头描述先假定 a≥b；上面的代码不要求预排序，a<b 时第一轮会交换两者。

为什么正确：先看数字

减去几个 6，为什么答案没变？

26 − 4 × 6 = 2

沿着计算看

如果一个数 d 能整除 26 和 6，它也能整除两者的整数倍之差。

d ∣ 26，d ∣ 6
所以 d ∣ 2

再反过来看

如果 d 能整除 6 和 2，它也能整除 4 × 6 + 2。

d ∣ 6，d ∣ 2
所以 d ∣ 26

(26, 6) 与 (6, 2) 的公约数，一个也没丢，也没多。

讲解提示

先用同一组数字建立双向直觉，下一页再换成字母。这不是只拿 d=2 验证一次，而是在说“任意一个公约数 d”。

为什么正确：把理由写完整

两边的公约数集合相同

设 a = qb + r。对任意正整数 d，分别证明两个方向。

已知 d 整除 a、b

写成 a = md，b = nd。

r = a − qb
= (m − qn)d

所以 d 也整除 r。
它是 b、r 的公约数。

已知 d 整除 b、r

写成 b = nd，r = kd。

a = qb + r
= (qn + k)d

所以 d 也整除 a。
它是 a、b 的公约数。

公约数集合相同，最大值也相同：gcd(a, b) = gcd(b, r)

讲解提示

两个方向都要讲到。单向只能保证一边的公约数仍然保留，不能直接推出集合相同。这里完整展开“为什么仍是 d 的倍数”，方便投屏时逐行讲。

为什么会停

为什么它一定会结束？

每一轮，第二个数从 b 变成余数 r。

0 ≤ r < b

非负整数不可能永远严格下降，
所以第二个数会在有限步后到达 0。

(26, 6)

(6, 2)

(2, 0)

每轮答案不变，最后到达 gcd(a, 0) = a。

讲解提示

把两件事分开：公约数不变保证没有算错；非负整数严格下降保证不会死循环。两个理由加上终点的答案，才构成完整论证。

回到定义

现在再看“算法”这句话

问题说清楚，
步骤可以一步步执行。

这一类问题

任意两个正整数的最大公约数。

这一套步骤

反复取余、替换，直到第二个数为 0。

它的保证

答案不变，有限步结束，返回所需结果。

换一门编程语言，或换一组输入，仍然可以是同一个算法。

讲解提示

回到抽象定义。先让大家看到一个完整实例，再体会什么叫“一类问题”和“一套步骤”。接下来才开始比较好坏。

另一种正确算法

每次只减一次，可以吗？

把两数排成 a ≥ b。当 b > 0 时，用 a − b 替换 a，再重新排序。

gcd(a, b) = gcd(a − b, b)

答案仍然不变

d 整除 a、b，就整除 a − b。
d 整除 a − b、b，就整除 (a − b) + b = a。

也一定会结束

每步让 a + b 减少一个正数 b。
总和是非负整数，所以不能一直减下去。

本讲相等时继续减到零：(2, 2) 变成 (2, 0)。若改成相等即停，步数会不同。

讲解提示

把证明直接展开，说明减法为什么也成立。减法版本不要跟踪较小数：它可能几轮不变。跟踪 a+b 才能清楚证明严格下降。

差别来自哪里

一次取余，合并了多次减法

每次减一个 6

26 − 6 = 20
20 − 6 = 14
14 − 6 = 8
8 − 6 = 2

一次拿走四个 6

26 mod 6 = 2

等价于 26 − 4 × 6。

两种方法都会到达 (6, 2)，
只是走到这里的步数不同。

先猜一猜：一直算到第二个数为 0，各需要几步？

讲解提示

先比较第一段 4 次减法与 1 次取余。再让大家猜整段，下一页运行验证。一次取余与一次减法在这里各计一步，这只是我们选定的计数方法。

一起运行

相同的答案，不同的步数

取余法

0 次取余

  1. (26, 6)

减法

0 次减法

  1. (26, 6)

两种方法各做一次运算；先完成的一侧会停下。

每次取余或减法计 1 步，交换不计。输入范围 1–9999；长轨迹显示最近 4 个状态，柱长按最终总步数比较。

讲解提示

先用 (26,6) 逐步运行：2 次取余、7 次减法。再选 (9999,1)，点“前进1000步”，让大家看到减法还远没有结束，最后点“运行到底”。不要把操作次数说成实际耗时。输入交换不计步数。

分清两种“好”

答案有多好，与算得多快

问题对答案的要求

例如：找最短路径。

“最短”描述路径长度，是我们要得到的答案的性质。

求最大公约数时，两种算法都必须返回同一个正确整数。

算法消耗的计算资源

例如：求出答案要几步。

这是计算过程的成本，还可以关心时间、内存等资源。

得到相同的正确答案，可以花不同的计算成本。

先明确要什么答案，再比较求出它的成本。

讲解提示

如果有人问“最短的不一定是最对的？”，解释：最短路径的“短”和计算过程的“快”是两个维度。算法也不都在找某个最优解，比如排序、判断整除、采样各有不同目标。

为复杂度做准备

我们到底在数什么？

输入取余法减法
(26, 6)2 次取余7 次减法
(9999, 1)1 次取余9999 次减法

这说明所选输入上的操作次数不同，
还没有证明哪个算法在所有场景下最快。

一次取余与一次减法，代价未必相同。数字越长，一次算术运算本身也可能越贵。

GCD 还有二进制、Lehmer、Half-GCD 等方法，大整数库会按输入规模选用不同算法。[6]

讲解提示

不能据此说“取余法理论上已经最快”。我们证明了正确与终止，用例子比较了次数，但没有建立计算模型，更没有证明最优性。下一讲可以从这里正式引入复杂度。

回到熟悉的工作

再回答开场的 ChatGPT 问题

先选定其中一个过程，再问：
它解决什么问题？具体步骤是什么？

例如：采样下一个 token

给定一个概率分布，按明确规则选择一个 token。即使结果带有随机性，步骤也能写清楚。

例如：训练更好的模型

“更好”需要先落实为任务与评价标准，再确定数据处理、训练和实验的步骤。

把模糊目标变成明确问题，本身就是工作的一部分。

讲解提示

联系算法工程师的工作：真实工作的目标往往一开始并不清楚。要区分工作的开放性，与某个具体算法的定义。也不要把“生成过程可执行”当成“生成的自然语言一定正确”。

今天先留下这个问题

下一讲：怎么数计算量？

How do we count
computation?

输入变大以后，计算量怎样增长？

先选定要数的操作，再看它与输入规模的关系。
有了这个直觉，再引入大 O。

课后小问题：输入 (n, 1)，两种算法各需要几步？

讲解提示

答案：n 是正整数，按本讲减到零的约定，取余 1 次，减法 n 次。这里 n 是数值大小；若按二进制位数衡量输入规模，还要再换一层视角。留到下一讲展开。

课后查阅

参考资料

  1. NIST · Algorithm

    可计算步骤的定义，以及 algorithm 一词的来源。

  2. NIST · Randomized algorithm

    算法可以包含随机或伪随机选择。

  3. Brown et al.（2020）· Language Models are Few-Shot Learners

    自回归语言模型的训练与使用，作为本讲简化例子的依据。

  4. Ouyang et al.（2022）· Training language models to follow instructions with human feedback

    监督微调与人类反馈训练，说明训练还可以有不同目标和流程。

  5. Euclid · Elements VII.2（David Joyce 整理）

    最大公度的求法与证明；互质情形见 VII.1。本讲使用现代记号。

  6. GNU MP · Greatest Common Divisor Algorithms

    二进制 GCD、Lehmer 与 Subquadratic GCD。支持“取余法不等于所有场景下的最优实现”这一区分。

数学例子与证明按本讲约定推导。模型部分仅用于解释基本概念，不代表当前产品的完整内部实现。

附录

本讲的计算约定

讲者提示