02.01 离散对象与成本模型：估算一批 IM 消息的工作量
返回第二卷 · 先修：01.04 数组、切片与文本 · 学习路线
本章的数字、代码与输出是按明确假设推导的教学预期。我们没有运行消息服务或测量性能；任务数量、操作次数和真实耗时分别讨论。
本章怎样学习
01.04 已经把多条消息放入数组和切片，并学会逐项遍历。现在遇到新问题：一个群有多名成员，每名成员可能有多台设备，一批消息还可能触发重试。程序究竟要处理多少个对象？规模扩大后，工作量怎样变化？
本章从自然语言和小整数出发，逐步建立数学工具。只要求会变量、条件、普通函数、循环、数组和切片；结构体、map、指针、并发、网络和数据库均不是先修。
| 阅读层次 | 内容 | 本次目标 |
|---|---|---|
| 第一遍起步 | 一、对象与逻辑；二、计数与单位 | 说清数什么，列出不重复的任务 |
| 第一遍推导 | 三、求和与对数；四、成本模型 | 从小表推导数量与基本操作 |
| 第一遍应用 | 五、增长界 | 正确解释 O、Ω、Θ |
| 第二遍深化 | 六、最坏/平均/摊还；七、概率 | 区分不同问题与前提 |
| 第二遍证明 | 八、归纳与不变量 | 解释为什么对一类输入成立 |
| 综合练习 | 九、工作量评审与分层题 | 独立改变假设，重新推导 |
第一次学到第五节后，可以先完成第九节的起步题。第六至八节适合分次学习，不要求在刚认识集合时同时掌握概率与证明。后面的算法章节会继续使用并深化这些工具。
一、先认识对象，再谈集合和逻辑
1.1 “有三个”必须说明三个什么
离散对象是可以逐个区分的对象。本章数的是一位位用户、一台台设备、一条条消息以及一次次操作。它们可以用整数计数，但同为数字 3，并不表示同一件事。
| 对象 | 本章含义 | 例子 |
|---|---|---|
| 用户 | 一个账号主体 | u-a |
| 设备 | 本模型中归属某个用户的终端身份 | d-a1 |
| 消息 | 有独立身份的一条业务消息 | m-1 |
| 投递任务 | 要将某条消息交给某台目标设备的计划 | 消息 m-1 与设备 d-b1 这一对 |
| 尝试 | 执行某个任务的一次动作 | 该任务的第一次、第二次尝试 |
这里先用纸面身份表示对象，还没有实现完整消息结构。消息 m-1 与 m-2 的正文都可以是“你好”，但它们仍是两条消息；同一条 m-1 面向三个设备，仍是一条消息，只是形成多个任务。
一次任务重试，并不自动创建一条新的业务消息。若把这些对象混成同一数字，后面就容易把“处理了 100 次尝试”误说成“收到 100 条不同消息”。
1.2 集合不关心排列，也不重复保存同一元素
集合是一组确定的对象，每个对象称为元素。写成 U={u-a,u-b,u-c}，意思是 U 包含三位用户。u-b ∈ U 读作“u-b 属于 U”。|U| 表示集合元素数，这里等于 3；它不是绝对值计算，而是这个语境中的集合大小。
集合有两个重要特征：不靠先后顺序区别集合，同一元素重复写出也不增加大小。因此 {u-a,u-b} 与 {u-b,u-a} 表示同一集合，{u-a,u-a,u-b} 也只有两个不同元素。
空集没有任何元素，写作 ∅，大小是 0。
回看 Go 切片。下面是 main 内片段，文件需要导入 fmt：
users := []string{"u-a", "u-a", "u-b"}
fmt.Println(len(users)) // 预期：3len(users) 为 3，因为切片里有三个位置。若我们想数“不同用户”，只有两个。数学集合是一种对象描述，切片是有位置、允许重复的数据表示；二者不能仅凭一个 len 自动等同。以后将学习如何实现去重，现在先把要数的对象说清。
1.3 关系描述两个对象之间是否成立某件事
有序对是按位置放在一起的两个对象，例如 (u-b,d-b2)。第一个位置表示用户，第二个位置表示设备；交换位置就改变了含义。
关系是一组符合特定条件的有序对。例如“设备归属用户”可以用完整快照表描述：
| 用户 | 当前归属设备 |
|---|---|
| u-a | d-a1 |
| u-b | d-b1、d-b2 |
| u-c | d-c1 |
本例约定表格完整，每台设备归属一个用户，一个用户可以有多台设备。于是 (u-b,d-b2) 属于这份关系，(u-a,d-b2) 不属于。
“表格完整”是一项必要前提。如果只拿到部分数据，表中没有一对关系，可能仅仅表示尚未记录，不能立刻断言它不存在。数学模型常假设拿到完整输入；真实业务要另行确认数据范围。
这只是关系的定义，不要求使用 Go map。当前阶段可以画表来推理，不必为了表达一个数学概念提前引入新语法。
1.4 并、交、差帮助我们避免重复计数
设 A={u-a,u-b,u-c}，B={u-b,u-c,u-d}：
| 运算 | 含义 | 本例结果 |
|---|---|---|
| 并集 A∪B | 在 A 或 B 中，包括同时在两者中 | u-a、u-b、u-c、u-d |
| 交集 A∩B | 同时在 A 与 B 中 | u-b、u-c |
| 差集 A\B | 在 A 中但不在 B 中 | u-a |
如果要统计不同用户，不能直接用 3+3=6，因为 u-b、u-c 被各算了两遍。把重复部分减一次：
并集大小 = A 的大小 + B 的大小 - 交集大小
= 3 + 3 - 2
= 4只有确认两类对象不重叠时，才能直接用加法合并不同对象数。差集还有方向：A\B 是 u-a，B\A 是 u-d，交换顺序会得到不同结果。
1.5 命题、与或非，让假设可以被检查
命题是能判断真假的陈述。例如在上面完整表格中，“u-b 有两台设备”为真，“每位用户都有两台设备”为假。
deviceCount > 0 带有未确定的变量，要代入某位用户的设备数才能判断。我们也会把这种带参数的判断称为条件。
设 A 表示“会话类型已知”，B 表示“文本非空”：
| A | B | A 且 B | A 或 B | 非 A |
|---|---|---|---|---|
| 假 | 假 | 假 | 假 | 真 |
| 假 | 真 | 假 | 真 | 真 |
| 真 | 假 | 假 | 真 | 假 |
| 真 | 真 | 真 | 真 | 假 |
“且”要求两项都真；“或”要求至少一项真，允许两项同时真；“非”翻转真假。这与已学的 &&、||、! 相接。数学中的真假组合与程序还涉及的求值顺序是两个问题；Go 的短路求值会决定后一个条件是否执行。
“会话已知或正文非空”不是已有的消息接受规则，因为未知会话配非空文本就能满足它。用具体输入检查逻辑，比只看条件式长得像不像更可靠。
1.6 “所有”和“存在”分别需要什么证据
所有要求范围内每个对象都满足条件；存在要求至少找到一个满足条件的对象。这两个词是在说明判断的数量范围，也称为量词。
“所有用户都有两台设备”可以被 u-a 这个反例推翻。“存在用户有两台设备”只要给出 u-b 就能支持。反过来，找到一个成功例子不足以说明“所有”。
若在线设备集合为空：
- “所有在线设备都符合规则”在逻辑上为真，因为没有反例。
- “存在一台在线设备”是假，因为找不到这样的对象。
所以业务若要求至少一台设备，并且每台都符合规则，必须把“非空”和“全部满足”分别写出。否则一个空列表可能通过全部校验，却没有产生任何任务。
起步练习：候选切片为
[u-b,u-b,u-c]。它有几个位置、几个不同用户？如果 u-b 有两台设备，能直接把切片长度当作目标设备数吗？
二、先固定扇出模型，再数消息、设备和尝试
2.1 本章的群消息计数约定
扇出指同一消息形成多个目标方向的处理工作。本章先建立一个有限静态模型：
- 群成员为 u-a、u-b、u-c、u-d，发送者是 u-a。
- 排除发送者的全部设备，只统计另外三位成员。
- 接收方在线设备数依次为 2、0、1，各设备只计一次。
- 一批消息来自同一发送者，使用同一成员与在线设备快照。
- 每条消息为每台目标设备产生一个初始任务。
- 此处只数计划工作，不发生网络发送，也不证明设备收到。
| 成员 | 是否计入接收方 | 在线设备数 | 每条消息的初始任务数 |
|---|---|---|---|
| u-a | 否，发送者 | 本模型不使用 | 0 |
| u-b | 是 | 2 | 2 |
| u-c | 是 | 0 | 0 |
| u-d | 是 | 1 | 1 |
此处有 4 名群成员、3 名接收用户、3 台目标设备。后两个数相等是巧合，不能替代各自定义。若 u-b 又多一台在线设备，接收用户仍为 3，目标设备却变为 4。
u-c 当前不产生在线任务，也不能由此得出“其离线消息被丢弃”。离线保存与后续补拉没有进入本模型，需要在相应课程中增加新的规则。
2.2 加法数不同接收方，乘法数消息与设备的组合
先合并各接收方不重叠的设备：
目标设备数 D = 2 + 0 + 1 = 3再给三条不同消息分别建立计划：
| 消息 | 给 u-b 的任务 | 给 u-c 的任务 | 给 u-d 的任务 | 小计 |
|---|---|---|---|---|
| m-1 | 2 | 0 | 1 | 3 |
| m-2 | 2 | 0 | 1 | 3 |
| m-3 | 2 | 0 | 1 | 3 |
| 合计 | 6 | 0 | 3 | 9 |
乘法计数把每条消息都有的 D 个选择重复 n 次，得到 Q=n×D 个不同的“消息、设备”组合。某条消息给设备 d-b1，与另一条消息给 d-b1，是两个不同任务。
乘法需要前提：这里每条消息对应同一份目标集合。若三条消息分别面向 3、2、4 台设备，应计算 3+2+4=9；不能拿其中一个设备数直接乘以 3。
2.3 量纲是检查公式含义的工具
量纲或单位说明数字在量什么。3 条消息+3 台设备 没有自然的“任务数”含义；得到算术结果 6，并没有得到一个成立的业务公式。
在本章规则下，D 台目标设备为每条消息产生 D 个任务，因此可以写：
3 条消息 × 3 个任务/条消息 = 9 个任务如果把第二项写成“3 台设备/条消息”，约掉消息后只能得到设备单位，不能悄悄把它改叫任务。更完整的表达是：每个“消息×设备”的组合产生 1 个任务；规则提供了组合与任务之间的对应。
同理，若每个初始任务仅按正文计算 100 字节，9 个任务对应 900 字节的逻辑正文副本量。它未包含协议开销、合并、压缩和重试，不能直接当作线上实际传输字节。
2.4 任务、队列项、网络包不一定一一对应
本章把消息与目标设备的组合称为任务，是为了明确业务工作量。实际实现可能把一个群的多个目标装进一项队列记录，也可能在多个阶段拆成多项；队列项只是某个待处理列表中的一条记录。
网络包是传输层次上的单位，也不必与一条业务消息或一项任务相同。本章没有规定怎样编码、分包和合并，因此不能从 9 个任务直接宣布“会产生 9 个网络包”。
同样，9 个逻辑投递目标不等于已经完成 9 次交付。任务描述“计划做什么”，确认与失败处理才会提供“实际做到什么”的证据。
2.5 首次尝试与额外重试分开数
设每个初始任务都至少执行一次；之后可能额外重试。令 Q 为初始任务数，R 为总额外重试次数，则：
总尝试数 A = Q + R9 个任务中，一个任务多试两次，其余只试一次，得到 11 次尝试。若两个任务各多试一次，也得到 11 次；任务数仍为 9。
“每任务最多重试 2 次”意味着首次之后还可执行两次，所以每个任务总尝试最多 3 次。在所有任务都执行首次、重试不超过限制的前提下：
Q ≤ A ≤ 3Q
9 ≤ A ≤ 2727 是许可范围内的上界，不是每次必然发生的数量。如果调度策略可能在首次前取消任务，连“至少 Q 次”也要重新核对。这说明上界、实际值和模型前提必须一同记录。
2.6 批次改变分组，不自动减少任务
批次是把若干项工作作为一组处理。设每批最多装 b 项，b 必须是正整数。9 项、每批最多 4 项，可以分为 4、4、1，共 3 批。
用数学写法表示为 ⌈9/4⌉=3。⌈x⌉ 叫向上取整，表示不小于 x 的最小整数；⌊x⌋ 叫向下取整，表示不大于 x 的最大整数。例如 ⌈2.25⌉=3，⌊2.25⌋=2。
| 工作项数 | 每批上限 | 最少批数 | 最后一批项数 |
|---|---|---|---|
| 0 | 4 | 0 | 没有批次 |
| 1 | 4 | 1 | 1 |
| 4 | 4 | 1 | 4 |
| 5 | 4 | 2 | 1 |
| 9 | 4 | 3 | 1 |
| 11 | 4 | 3 | 3 |
公式 ⌈Q/b⌉ 计算在可以任意组合、除末批外都装满时的最少批数。若按设备分组、受等待时间限制而提前发送，实际批数可以更多；若重试必须等前次结果，也不能预先把所有尝试任意塞进同一批。
批量可能减少某些固定开销，但 9 项工作分成 3 批后，仍然有 9 项。没有说明批处理机制和测量结果，不能由批数宣布延迟缩短为三分之一。
三、用求和、指数和对数表达重复
3.1 求和符号只是“按规则把各项加起来”
若接收用户数为 m，第 i 位用户有 d_i 台目标设备，总数写作：
大写希腊字母 Σ 表示求和；下面 i=1 表示从第 1 项开始，上面 m 表示到第 m 项结束；d_i 是第 i 项的值。对 [2,0,1]，它展开后就是 2+0+1。
| 已处理项目 | 本次加入 | 累计设备数 |
|---|---|---|
| 0 项 | 尚未加入 | 0 |
| 第 1 项 | 2 | 2 |
| 第 2 项 | 0 | 2 |
| 第 3 项 | 1 | 3 |
没有接收用户时，空求和约定为 0，正好对应循环没有进入、累计值仍为 0。这里用第 1、第 2 项方便数学阅读；Go 切片对应下标 0、1，翻译时需要保持这个差别。
若各条消息面向不同快照，第 j 条消息的任务数是 D_j，总任务应写成 Σ D_j。所有 D_j 都等于同一个 D 时，求和才简化成 nD。
3.2 两两处理先说清是否有方向、是否包含自己
有 4 条不同消息，想比较每两条的某种属性。只比较不含自己的无序对，可以列出：
(1,2) (1,3) (1,4)
(2,3) (2,4)
(3,4)共 3+2+1=6 对。若 (1,2) 和 (2,1) 表示相同的比较，就不能重复计数；若业务把两个方向视为不同任务，则应分别计入。
| 组合要求 | n 项的数量 | n=4 |
|---|---|---|
| 有方向，允许自身 | n² | 16 |
| 有方向，不含自身 | n(n−1) | 12 |
| 无方向，不含自身 | n(n−1)/2 | 6 |
n² 读作 n 的平方，表示 n 乘 n。n 为 0 或 1 时，无方向不含自身的数量都为 0。零对不等于“程序一定零开销”，它只表示所选基本比较没有发生。
3.3 为什么 1 到 n 的和是 n(n+1)/2
把同一列数正着与倒着排列：
正序： 1 2 3 ... n
倒序： n n-1 n-2 ... 1
每列：n+1 n+1 n+1 ... n+1一共有 n 列，每列和为 n+1，所以两份和共为 n(n+1)，一份就是 n(n+1)/2。取 n=4，1+2+3+4=10，公式也给出 4×5/2=10。
前一节的无序对数是 1+2+…+(n−1)，把这里的 n 换成 n−1，就得到 n(n−1)/2。推导来自怎样枚举对象，不是看到两层循环就随手写一个平方。
3.4 指数表示不断相乘，对数反过来数次数
2^k 在本章的数学文字里表示 k 个 2 相乘，例如 2^3=8；当 k=0 时定义为 1。Go 的 ^ 不表示乘方，不要把数学记号直接抄成 Go 表达式。
| 倍增次数 k | 数量 2^k |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
反过来，“2 的几次方等于 16”，答案是 4，写作 log₂16=4。这就是以 2 为底的对数。对正数，它回答从 1 按倍增尺度走到这个数量需要多少层；结果不一定是整数。
例如 8 小于 12、12 小于 16，因此 log₂12 在 3 与 4 之间。很多程序只做整数轮操作，此时需要结合具体取整与停止条件判断轮数。
3.5 折半模型为什么得到向上取整
本模型规定：当剩余候选数大于 1 时，保留一半；若不能整除，保留较大的那半，即向上取整。只数这种缩小操作的轮数：
| 起始数量 | 每轮之后 | 轮数 |
|---|---|---|
| 1 | 已到停止条件 | 0 |
| 2 | 1 | 1 |
| 5 | 3 → 2 → 1 | 3 |
| 8 | 4 → 2 → 1 | 3 |
| 16 | 8 → 4 → 2 → 1 | 4 |
对正整数 n，轮数为 ⌈log₂n⌉。原因是做 k 轮后，最多还剩 ⌈n/2^k⌉；需要让它变为 1，就要使 2^k ≥ n，最小整数 k 正是向上取整后的对数。
n=0 时本模型直接约定没有候选、需要 0 轮，不计算 log₂0。若改成每轮向下取半且仍以剩余不超过 1 为停止条件，5 会走 5→2→1，轮数变成 2。说明 floor/ceil 不是随便挑的装饰符号。
这个模型只解释折半带来的增长速度。真正的二分搜索还需要有序数据、有效比较与正确的区间更新，使被丢掉的一半确实不含答案。完整算法放在 02.03，本章没有给任意消息列表套上对数搜索保证。
3.6 等比求和与几种增长的对照
倍增序列的前几项为 1+2+4+8=15。若把总和 S 乘 2，再减去 S，中间项抵消，得到 S=16−1。一般写成：
它稍后用来计算不断扩容时的累计复制量。先比较一些增长模式的具体数值：
| 规模 n | 固定 1 | log₂n | n | n·log₂n | n² |
|---|---|---|---|---|---|
| 8 | 1 | 3 | 8 | 24 | 64 |
| 16 | 1 | 4 | 16 | 64 | 256 |
| 32 | 1 | 5 | 32 | 160 | 1024 |
规模翻倍，线性数量翻倍，平方数量变为四倍，对数只加 1。表中是数学数量，不能直接把 1024 写成 1024 毫秒；要先说明每个数量到底对应什么操作。
四、成本模型：明确数哪种基本操作
4.1 输入规模可以不止一个数
输入规模是描述输入大小的数量。常用 n 表示，但字母没有固定业务含义。我们在本章统一约定：
| 符号 | 本章含义 |
|---|---|
| n | 本批消息条数 |
| m | 已排除发送者后的接收用户项数 |
| d_i | 第 i 位接收用户的在线设备数 |
| D | 目标设备总数，等于各 d_i 的和 |
| B | 一批消息正文的总字节数 |
| Q | 初始任务数，在同快照模型下等于 nD |
两批都是 100 条消息，一批每条 10 字节，另一批每条 10000 字节，n 相同，B 却分别为 1000 和 1000000。若每个字节都要检查，只知道消息条数就不够。
同样，m=3 不一定意味着 D=3。设备列表 [2,0,1] 与 [3,2,1] 都有三个用户项，却分别有 3、6 台目标设备。公式里的符号必须保持含义，不能写到一半把 m 从用户数换成设备数。
4.2 基本操作是我们选定的计量单位
成本模型规定把哪些动作作为基本单位，怎样累加它们的次数。例如可以数一次整数相等比较、一次元素写入，或者一次正文的字节检查。
为解释下面的小程序，我们暂时把读取一个整数元素、固定宽整数的比较/加法/乘法分别当作常数成本动作。这个假设让我们可以比较数量增长；它不声称每种动作真实耗时相等，也不声称一行 Go 只有一个机器动作。
经典算法教材同样要求先说明基本操作与成本模型，再讨论增长；测量与模型预测需要分别说明。Algorithms 4e：算法分析
一个具体例子是字符串：
len(s)读取字符串字节长度，并不要求逐个解码字符。在这里的模型中按固定成本计。- 扫描 s 的所有字节，需要随字节数增长的检查。
s == other可能检查可变长度的内容。不能因为只写一个比较表达式，就无条件当作与字符串长度无关。
后面线性查找的比较例子使用小整数作为教学标识。若换成长度可变的消息 ID 文本，就要补上键长度的条件，或把单次字符串比较成本一并计入。
4.3 用已经学过的切片做一个有界计数器
下面函数只算数量。调用者提供的切片必须已经排除发送者，每项对应一位不同的接收用户；函数仅凭设备数无法验证这些身份前提。
教学输入范围规定：消息数 0–1000，最多 1000 个接收用户项，每项在线设备数 0–10。这些限制用于让算术结果有明确范围，不是 IM 生产容量建议。
可新建 im-cost 目录，按第一章的方法准备模块 example.com/im-cost，将完整程序保存为 main.go：
package main
import "fmt"
func countInitialTasks(messageCount int, onlineDevices []int) (int, bool) {
if messageCount < 0 || messageCount > 1000 {
return 0, false
}
if len(onlineDevices) > 1000 {
return 0, false
}
devices := 0
for _, deviceCount := range onlineDevices {
if deviceCount < 0 || deviceCount > 10 {
return 0, false
}
devices = devices + deviceCount
}
return messageCount * devices, true
}
func main() {
onlineDevices := []int{2, 0, 1}
tasks, ok := countInitialTasks(3, onlineDevices)
if !ok {
fmt.Println("拒绝：计数输入超出教学范围")
return
}
fmt.Println("初始任务数：", tasks)
}预期输出：
初始任务数： 9第二个返回值先说明结果是否有效。0, true 可以表示没有消息或没有目标设备；0, false 表示拒绝输入，前面的零不能被当成已经计算出的任务数。
4.4 跟踪数值与操作，是两张不同的表
在 [2,0,1] 上：
| 当前项 | 范围是否允许 | 加入前 devices | 加入后 devices |
|---|---|---|---|
| 2 | 是 | 0 | 2 |
| 0 | 是 | 2 | 2 |
| 1 | 是 | 2 | 3 |
循环结束后再做 3×3=9。函数没有访问三条正文，也没有生成九个记录，只产生一个表示数量的整数。
对全部有效的 m 项输入，可以分别统计：
| 选定动作 | 次数 |
|---|---|
| 访问一个设备数元素 | m |
| 执行一次范围条件判断 | m |
| 把一项设备数加入累计值 | m |
| 用消息数乘设备总数 | 1 |
“范围条件判断”在这里当作一个抽象步骤，内部包含比较与短路；若选择更细的比较口径，次数会不同。循环条件、赋值、返回也有成本，所以这张表不宣称完整程序只做 m 次工作。
输入在第 k 项出现非法值时，只访问到第 k 项，其中前 k−1 项已经加进局部累计值，但函数返回拒绝，不交付这个不完整数量。调用者的切片没有被修改。
4.5 零输入与上界需要明确验收
| 输入 | 预期返回 | 解释 |
|---|---|---|
n=3，[2,0,1] | 9, true | 常规快照 |
n=2，[1,3] | 8, true | 用户项数 2，设备数 4 |
n=0，[2,0,1] | 0, true | 没有消息，仍检查所给设备数是否合法 |
| n=3，空切片 | 0, true | 没有接收用户项 |
n=3，[0,0] | 0, true | 有用户项但没有在线设备 |
n=-1，[1] | 0, false | 消息数非法 |
n=1001，[1] | 0, false | 超出教学范围 |
n=1，[-1] | 0, false | 设备数不能为负 |
n=1，[11] | 0, false | 超出每项上限 |
n=0，[-1] | 0, false | 零消息没有取消输入有效性检查 |
| n=1000，1000 项且每项 10 | 10000000, true | 合法最大组合 |
| n=1，1001 项且每项 0 | 0, false | 列表本身超限 |
合法数据中，设备总数最多 1000×10=10000，最终乘积最多一千万，在 32 位有符号整数范围内。我们先通过边界推导再允许乘法，不靠整数溢出后观察到什么结果来定义业务行为。
4.6 算出数量与生成所有记录不是同一份工作
计算 n×Σd_i，主要工作随 m 项设备数增长。如果 D 已经可信地计算好，单独求 nD 在当前整数模型中只需一次乘法。
如果要显式写出 Q 个任务记录，至少需要 Q 次记录写入；一个整数结果不能替代这些输出。若先扫描 m 项、再对每个任务做固定次数工作，整个模型成本为随 m+Q+1 增长。这里的 +1 保留了空输入时的固定开销。
因此“总任务数为一千万”不意味着计数函数也必须循环一千万次；“计数只扫描一千项”也不意味着已经创建了一千万项任务。
代码的 1000 限制是安全演示边界。后面讨论渐近增长时，将讨论允许规模继续增大的抽象算法模型，以足够容纳索引和计数的整数作为单位操作。不能把有限演示上限当作一个无穷规模证明；若数值位数本身也成为变量，需要另行计入多位整数运算成本。
五、从精确次数到 O、Ω、Θ
5.1 先给出一个明确的成本函数
成本函数把输入规模映射成所选操作的数量。先用抽象模型：每条消息做 3 个单位动作，开始有 2 个固定动作，得到 T(n)=3n+2。
这里的 3 和 2 是已经声明的计量安排，不是从前面的 Go 程序逐机器指令测出的结果。
| n | 逐条动作 3n | 固定动作 | T(n) |
|---|---|---|---|
| 1 | 3 | 2 | 5 |
| 10 | 30 | 2 | 32 |
| 100 | 300 | 2 | 302 |
| 1000 | 3000 | 2 | 3002 |
规模增大后，固定的 2 对总数量的占比越来越小。我们希望用一个较简单的函数描述增长，同时说明这个描述是上界、下界，还是两边都贴近的量级。
5.2 大 O 是最终成立的固定倍数上界
设 T(n) 非负，比较函数 f(n) 在足够大时为正。若能找到固定常数 c>0 和整数 n₀，使所有 n≥n₀ 都满足：
就写作 T(n)=O(f(n))。它读作：超过某个固定规模以后，T 不会超出 f 的某个固定倍数。MIT 6.006：算法效率与渐近记号
逐个解释定义中的条件：
- “存在”表示只要找到一组可用的 c、n₀。
- “所有 n≥n₀”表示之后的每个规模都要成立，不能只挑几个例子。
- c 与 n₀ 一旦选定就固定，不能跟着 n 每次变大。
- 开始的有限个小规模可由 n₀ 隔开，因为该符号描述长期增长。
对 T(n)=3n+2，n≥1 时有 3n+2≤5n，可以取 c=5、n₀=1，所以它属于 O(n)。
5.3 Ω 给下界，Θ 给同一量级的两边界
若存在固定 c>0、n₀，使所有 n≥n₀ 满足：
就写作 T(n)=Ω(f(n))。Ω 读作 Omega，表示最终至少达到 f 的某个正倍数。
若存在固定 c₁>0、c₂>0、n₀，使所有 n≥n₀ 满足：
就写作 T(n)=Θ(f(n))。Θ 读作 Theta，表示上下界属于同一个增长量级，也叫紧确界。
对同一个 3n+2：
n≥1 时：3n ≤ 3n+2 ≤ 5n所以它既为 Ω(n)，也为 O(n)，合起来为 Θ(n)。两个常数可以不同；不要求 T(n) 与 n 相等，也不要求操作只有一次。
5.4 上界可以正确但很松
由于 n≥1 时 n≤n²，上面的函数也满足 3n+2≤5n²，所以说它是 O(n²) 仍然正确，只是没有准确表达其线性增长。
但 n² 不是 O(n)。若存在固定 c 使所有大 n 都满足 n²≤cn，除以正数 n 就得到 n≤c。总能选择一个同时大于 c 和 n₀ 的整数，这会推翻不等式。
这段推理说明常数不能取成“c=n”。让 c 跟 n 变化会失去限制增长的作用，也违反定义。
5.5 符号不是“最坏”“最好”的别名
先选择你在讨论的成本函数，再给它上界或下界。例如可以先定义所有同规模输入中最大的成本 W(n)，也可以定义最小的成本 L(n)。之后分别写 W(n)=Θ(n)、L(n)=Θ(1)。
O 本身不会自动选择最坏输入，Ω 本身也不会选择最好输入。它们只是已经选定函数的增长边界。第六节会具体构造这些不同函数。
另一个常见误判是从“最多”跳到“恰好”或紧确界。若每条消息最多有固定 10 个任务，只能直接推出 Q≤10n，即任务数有线性上界。可能所有消息都没有目标，Q=0；仅凭上限不能推出 Q 总是 Θ(n)。
如果程序无论任务数多少，都至少检查每条消息一次，整体检查成本才另有 n 的下界。需要把这份额外工作写入模型，才能在适当前提下推出整体 Θ(n)。
5.6 多个规模变量保留各自含义
设 n 是消息数，D 是目标设备数：
| 工作安排 | 主要次数 | 解释 |
|---|---|---|
| 扫一遍消息，再扫一遍目标设备 | n+D | 两段独立工作相加 |
| 每条消息都查看每台目标设备 | nD | 消息和设备的组合 |
| 固定检查 100 个项目 | 100 | 不随 n、D 变化 |
且 n、D 均为正时，在每项工作为固定成本的模型下，前两种安排分别对应 Θ(n+D)、Θ(nD)。允许零输入后，需要重新查看循环控制：普通外层遍历 n 条消息、内层遍历 D 台设备的程序，在 D=0 时虽没有配对访问，外层仍推进 n 次，完整成本通常为 Θ(n+nD+1)。只有专门处理空维度后立即返回，或明确只数配对访问并加一个准备单位，才可在相应前提下写 Θ(nD+1)。同理，若还要预先扫描设备列表，其成本也应计入。
只有额外给出 D=n，nD 才变成 n²。若 D 是固定 10，nD 就随 n 线性变化。不要因为看到了两个名字，就默认二者相等；也不要因为暂时把 D 设成一个较小的整数，就宣称它在所有业务变化下永远固定。
5.7 增长级别不能直接排名所有小输入
比较两个已约定的成本函数：A(n)=100n，B(n)=n²。
| n | A(n) | B(n) |
|---|---|---|
| 10 | 1000 | 100 |
| 100 | 10000 | 10000 |
| 1000 | 100000 | 1000000 |
A 是线性，B 是平方，但在 n=10 时 B 的模型次数更少。渐近分析帮助判断规模持续增大后的趋势，实际选择还要结合输入范围、常数、内存和测量。
本章所数的操作不自动具有相同真实时间，表格也不能换个单位就变成延迟。后续性能分析会学习怎样测量并检验模型，现在先确保数学问题与业务对象一致。
六、第二遍：最坏、平均与摊还
6.1 相同规模也可能有不同成本
先研究线性查找的计数直觉，不展开 02.03 的完整搜索算法。列表中有 n 个不同的小整数消息标识，按顺序与目标比较，找到即停止；一次整数相等比较记作一个单位。
取列表 [12,18,23,31,44]：
| 目标 | 比较位置 | 比较次数 |
|---|---|---|
| 12 | 第 1 项 | 1 |
| 23 | 第 1、2、3 项 | 3 |
| 44 | 第 1 至第 5 项 | 5 |
| 99 | 全部都不相同 | 5 |
最坏情况是在规定的合法输入范围里，固定规模 n 后取最大的成本。这里目标可以不存在，或恰好在最后，所以最坏比较数 W(n)=n。n≥1 时的最好比较数为 1。
n=0 时不发生元素比较，比较数为 0；完整函数仍可能执行长度检查和返回，不能把“比较零次”说成“程序没有运行”。
“最近的消息经常排前面”是输入来源的信息，不会消除列表末尾或不存在这些合法情况。它可以进入平均模型，却不能单独降低这个最坏界。
6.2 平均需要先说明怎样抽取输入
分布说明各种可能输入出现的机会。用 0 到 1 的数表示某类结果的概率，1 表示全部机会，0 表示没有概率质量，概率之和为 1。第七节会继续解释这些概念。
先作明确假设：n≥1，目标保证存在，且在第 1 至第 n 个位置出现的机会相同，每个位置各为 1/n。此时平均比较数为：
n=4 时，四种成本是 1、2、3、4，等权平均为 2.5。任何单次查找都没有“比较半次”，小数来自不同结果的平均。
若目标有 80% 的机会在第一项、20% 的机会在第四项，平均变为 0.8×1+0.2×4=1.6。同样 n=4，分布改变后平均就不同；不能只记住“线性查找平均一半”而省略前提。
6.3 把“目标不存在”也纳入平均模型
设 n≥1，抽取输入时以概率 q 选择一个不存在的目标；剩下概率 1−q 选择已存在目标，并使各位置等可能。q 在 0 与 1 之间，包含两端。
- 不存在分支花 n 次比较。
- 存在分支的平均为
(n+1)/2。
合起来的加权平均是：
n=10、q=0.2 时，得到 0.2×10+0.8×5.5=6.4 次。q=0 回到保证存在的模型；q=1 时总是不存在，成本为 10。n=0 没有“均匀选择一个已有位置”的可能，必须另行使用空列表的 0 次比较结论。
这些公式是分布成立时的成本预测。它们不能代替对真实查询来源的调查，更不是每次请求都会执行的小数次数。
6.4 摊还分析观察一串操作的总成本
摊还分析研究某种允许的操作序列，把整串操作的成本分摊到各次操作。它可以不涉及任何随机性。定义初始状态与操作规则以后，要约束的是任意符合这些规则的序列。
用一个教学动态数组模型：
- 初始长度为 0、容量为 1。
- 连续在末尾放入固定大小的元素，不删除。
- 容量满时换成两倍容量，将旧元素逐个复制过去。
- 每次写入新元素记 1 单位，每复制一个旧元素也记 1 单位。
- 当前只数这些元素动作，不把内存分配器的真实运行时间混入数字。
这里的容量翻倍是模型规则，不是 Go append 固定保证。 01.04 已经说明 Go 不能按固定增长倍率推断实际容量。
| 第几次插入 | 插入前长度/容量 | 复制旧元素数 | 新写入数 | 本次成本 |
|---|---|---|---|---|
| 1 | 0/1 | 0 | 1 | 1 |
| 2 | 1/1 | 1 | 1 | 2 |
| 3 | 2/2 | 2 | 1 | 3 |
| 4 | 3/4 | 0 | 1 | 1 |
| 5 | 4/4 | 4 | 1 | 5 |
| 6 | 5/8 | 0 | 1 | 1 |
| 7 | 6/8 | 0 | 1 | 1 |
| 8 | 7/8 | 0 | 1 | 1 |
八次新写入加上 1+2+4 次复制，共 15 个单位，平均分摊为 15/8。第五次单独比较昂贵，摊还并没有删除它的成本。
6.5 从八次例子推到任意 N 次插入
用 N 表示从空结构开始的插入次数，N≥1。结束容量 C 是至少容纳 N 的最小 2 的幂，因此 N≤C<2N。所有扩容复制量为：
1 + 2 + … + C/2 = C - 1 < 2N当 C=1 时没有复制，左边按空和为 0，等式仍适用。加上 N 次必要写入，总成本至少 N、少于 3N。因此整串成本是 Θ(N)，每次摊还 Θ(1)。MIT 6.006：动态数组与摊还分析
注意总成本不是永远小于 2N。例如第九次触发从容量 8 到 16 的扩容，九次总成本为 9+(1+2+4+8)=24，超过 18，却仍少于 27。
若已有 n 个元素且容量正好已满，下一次仍要复制 n 个旧元素，单次成本为 n+1。摊还常数不能用来承诺每一次操作都不会遇到线性工作量。
这个结论依赖初始为空、只做末尾插入、容量按指定规则增长。如果任意一次之前都人为放置一个已经装满的大数组，再把之前的积累忽略，不能直接沿用上述分摊保证。
6.6 三种分析各自在回答什么
| 分析 | 对象与前提 | 不能省略的内容 |
|---|---|---|
| 最坏 | 同规模、同合法输入范围中的最大成本 | 输入范围、计量单位 |
| 平均 | 根据已说明分布的加权平均成本 | 各种输入的机会 |
| 摊还 | 从指定初始状态开始的整串操作成本 | 允许的操作与状态演变规则 |
最坏值也可以用于一串操作：我们刚刚约束了所有符合规则的 N 次插入序列的总成本。它与“单次最坏”不是同一个观察范围。
平均与摊还都会出现除法，却不能因此等同。平均分析按概率权重比较不同输入；摊还分析把同一串允许操作的总量分配出去，扩容完全可以在确定位置发生。
七、第二遍：概率、条件与期望
7.1 观测比例与概率参数不同
某批 10 个任务有 2 个需要额外尝试，本批比例是 2/10=20%。这是对已经给定数据的总结。它不能推出下一批也一定有两个，更不能直接证明未来真实概率就是 0.2。
样本空间是一次模型中列出的所有可能结果；事件是我们关心的一组结果。例如只关注“是否需要一次重试”，可以列出两个结果：不重试、重试。
两个结果不意味着机会各半。只有明确约定所有基本结果等可能，才能通过“符合事件的结果数÷全部结果数”计算概率。重试与不重试没有天然等可能性。
本节使用有限模型并明确给每个结果概率。对于“未来需要重试的概率 p=0.2”，它是一个需说明来源与适用范围的假设，而不是这段课程已经测出的生产事实。
7.2 随机变量把可能结果映射成数字
随机变量是为各个可能结果赋予一个数值的规则。它不是 Go 中“会自己随机变化的变量”。例如 X 记录某个任务的尝试次数。
现在把策略写得精确：每个任务执行一次首次尝试；若满足重试条件，一定再执行一次；之后停止。p 表示满足该条件的概率。我们只计执行次数，不要求第二次一定成功。
| 结果 | X 的值 | 概率 |
|---|---|---|
| 不进入重试 | 1 | 1−p |
| 执行一次重试 | 2 | p |
如果策略只是“允许最多一次重试”，但可能取消、不再执行，那么 p 必须改为实际执行额外尝试的概率，不能直接使用失败概率代替它。公式依赖事件定义与策略一致。
7.3 期望是按概率加权的数值
期望把每种数值乘以其概率再加起来。在上表中：
E[X] 读作 X 的期望。p=0.2 时得到 1.2。它描述模型的加权平均，不是要求某个任务实际执行 1.2 次。MIT 数学教材：期望定义
p=0 时始终一次，p=1 时始终两次，这两端可以检查公式是否与策略一致。期望不能单独告诉我们最大值、波动或连续失败会怎样聚集。
7.4 总期望相加，不要求各任务独立
有 Q 个任务，第 i 个任务尝试次数为 X_i，总次数 A 是它们的和。对这里有限且有界的变量：
这称为期望的线性性。每个任务 p=0.2 时，10 个任务的总期望为 10×1.2=12。这里不需要假定任务互相独立。
若重试概率分别为 0.1、0.2、0.4，三个任务的期望总数为 3+0.1+0.2+0.4=3.7。这是相加，不是在乘各任务的概率。
再用一个有强关联的反例：一批 10 个任务以 0.8 的概率全部不重试，以 0.2 的概率全部重试。总次数只可能是 10 或 20，却仍有期望 10×0.8+20×0.2=12。这批根本不可能恰好执行 12 次，期望仍可以等于 12。
仅声明每个任务有相同概率，也不足以保证长期实测比例在任意相关方式下必然接近它。要讨论样本平均的收敛，需要补充抽样与依赖条件；本节只使用有限概率表计算期望。
7.5 独立时，联合概率等于各自概率的乘积
设事件 A 是“设备甲的本次尝试按教学标准得到确认”，事件 B 是设备乙的对应事件。确认代表什么必须先在业务契约中定义；本节不把它当成人类已读。
独立在这里表示一个事件是否发生不改变另一个事件的机会。独立时，两者都发生的概率可以相乘。假设每个事件概率都是 0.9：
| 教学分布 | 两者都得到确认 | 只有甲 | 只有乙 | 两者都未得到确认 |
|---|---|---|---|---|
| 相互独立 | 0.81 | 0.09 | 0.09 | 0.01 |
| 总是同成同败 | 0.9 | 0 | 0 | 0.1 |
两行中，单独看甲的概率都是 0.9，乙也一样；两者都发生的概率却分别为 0.81 与 0.9。可见只知道各自概率，不能确定联合事件。
共同网络状况可能使多个任务有关联。若没有检查这个条件，直接将两个成功率相乘，会把某种独立模型擅自写成事实。
7.6 条件概率说明“已知一件事之后”的范围
条件概率把观察范围缩到已知事件之内。P(B|A) 读作“已知 A 发生时，B 发生的概率”。当 P(A)>0 时：
其中 A∩B 表示两件事同时发生。分母先把范围缩到 A，分子取其中也满足 B 的部分。MIT 数学教材：条件概率
对独立一行，0.81/0.9=0.9，得知甲确认不改变乙的机会；对同成同败一行，0.9/0.9=1，得知甲确认就确定乙也确认。P(A)=0 时，不能用这条公式除以零。
概率计算同样需要限定状态、时间段和观察对象。“一个任务最终得到确认”与“第一次尝试得到确认”是两个不同事件，不能在同一公式里悄悄替换。
八、第二遍：用归纳和不变量说明为什么成立
8.1 计算几个例子与证明一般结论不同
尝试 n=1、2、3，发现公式都成立，只说明这几个点没有推翻它。要说明每个允许规模都成立，需要覆盖全部规模的理由。
数学归纳法适合按自然数递进的结论。它包含：
- 基例：说明起点成立。
- 归纳步骤：对任意 k，假设第 k 项成立，据此推出第 k+1 项成立。
可以把它想成第一块台阶已经能站住，并证明任意一块都能到下一块。仅有起点或仅有“如果能上去就能继续”都不够。
8.2 重新证明 1 到 n 的求和公式
目标是对所有非负整数 n 证明 1+…+n=n(n+1)/2；n=0 时左侧为空和。
基例。 n=0，左右都是 0。
归纳假设。 取任意 k≥0，假定到 k 的和为 k(k+1)/2。
推出下一项。 到 k+1 的和是在旧和上增加 k+1：
结果正好是把公式中的 n 换成 k+1。于是每个非负整数都得到覆盖。
归纳假设并不是偷偷假设结论对所有 n 成立，而是在任意相邻两级之间证明一个条件关系，再由基例启动这个关系。该证明讨论数学整数，若把公式写进有限整数类型的程序，还需要检查乘法是否会溢出。
8.3 循环不变量给中间状态一个含义
循环不变量是在规定的循环观察点持续成立的性质。我们只看第四节求设备总数的成功路径。已知列表长度 m≤1000、各项在 0–10，总和不会溢出。
在已经处理前 i 项、准备处理下一项的时刻，声明：
devices 等于前 i 项设备数之和，其中 0≤i≤m。
“前 i 项”对应 Go 下标 0 到 i−1，不包含下标 i。把 [2,0,1] 的状态写出来：
| 已处理项数 i | 已处理下标 | devices |
|---|---|---|
| 0 | 无 | 0 |
| 1 | 0 | 2 |
| 2 | 0、1 | 2 |
| 3 | 0、1、2 | 3 |
初始化时没有处理任何项，累计为 0；若处理前不变量成立，加上当前项后，累计就变为前 i+1 项之和；成功结束时 i=m，得到全体之和。
如果中途遇到非法项，函数提前拒绝，不承诺交付完整和。拒绝路径与成功路径各自的后置条件不同，不能用“最后应该是全体之和”要求所有早退路径也返回一个有效计数。
8.4 正确结果还需要操作能够结束
不变量说明如果顺利处理到末尾，结果为什么正确。终止性说明不会永远停在处理中。
取尚未处理项数 m−i：开始非负，每处理一项就减少 1；列表在本模型中保持固定，最多 m 项后到 0，不能无限保持正数并每次减一。
若循环每次都累加同一个元素，却不推进位置，累计变量可能一直变化，却不会得到全部输入的和。若推进位置但漏加一项，可以结束，却算错。终止与结果正确需要分别解释。
这些证明只支持模型内的计数和控制过程，没有证明实际设备在线数据一定完整，也没有证明消息已经送达。输入前提、计算正确、业务效果分别需要对应证据。
九、把模型带回 IM 需求评审
9.1 完成一张有前提的工作量记录
回到三条消息、接收在线设备数 [2,0,1] 的快照。把几种结论分别放到自己的单位下：
| 要回答的问题 | 所需前提 | 推导结果 |
|---|---|---|
| 有几个接收用户项 | 已排除发送者，用户项无重复 | 3 项 |
| 有几台目标设备 | 每项是该用户不同在线设备的数量 | 2+0+1=3 台 |
| 有几个初始任务 | 三条消息使用同一快照，每对产生一项 | 3×3=9 个 |
| 实际安排几次尝试 | 每项都执行首次，另有 2 次额外尝试 | 9+2=11 次 |
| 初始任务最少分几批 | 每批最多 4 项，允许跨设备自由合并 | 3 批，4/4/1 |
| 十一次尝试的装箱下界 | 忽略重试时序，只按最多 4 项装箱 | 至少 3 批 |
| 按重试策略的尝试上界 | 每任务首次后最多额外两次 | 27 次 |
| 完成耗时多少 | 需要实际操作成本、调度与等待等资料 | 当前模型无法给出 |
对尝试的装箱下界，4/4/3 只是数学分组可能。若重试依赖前次返回、设备间不能混批或批次定时关闭，实际批数可能更大。评审时把下界说成实际安排，会掩盖没有建模的时序条件。
9.2 改一条需求，找出哪些项需要重算
若增加“给发送者另一台在线设备同步”的新需求，并且当前恰好增加一台目标设备：
- 接收成员项仍按原定义为 3；发送者同步单独作为新增方向。
- 每条消息的总目标数从 3 变成 4，初始任务由 9 变成 12。
- 原来的额外重试数 2 是旧批次信息，不能直接当作新批次必然值。
- 每任务最多额外两次的上界变为 36 次尝试。
- 若仍可任意装箱，12 个初始任务每批 4 项，最少 3 批。
初始批数碰巧没变，任务数却增加了。用一个“批数”指标代替所有工作量，会漏掉这种变化。
若改成每条消息具有不同的接收方，则应从 nD 回到逐条求和。若在线状态会变，先定义哪一个时刻的快照或怎样统计每条消息，才能知道新的 d_i 代表什么。
9.3 现在怎样对照主项目
这一章提供阅读 IM 实现之前的计数语言，不将某个数学模型宣称为 OpenIM 的真实队列或投递策略。继续阅读主项目时，可以带着这些问题寻找具体入口：
- 被遍历的元素究竟是用户、设备、连接、消息还是队列记录？
- 发送者怎样处理，同一用户多设备是否拆分？
- 在线状态在哪个位置取得，是否对整批一致？
- 队列一项包含一个目标还是多个目标？
- 重试计的是原消息、逻辑任务还是尝试？
- 代码有没有真正生成全部配对，还是只计算数量或写共享数据？
找到并核对具体代码以后，再把实际对象填进模型。本章没有新增关于上游扇出策略、复杂度或吞吐的源码结论。
9.4 分层练习与反馈
练习 1：集合与序列
切片中的用户依次为 u-b、u-c、u-b。位置数和不同用户数分别是多少？交换前两项后，用户集合是否改变？
参考反馈
位置数是 3，不同用户数是 2。交换位置会改变序列顺序，不改变它表示的用户集合。若业务按设备投递，还必须继续取得每个不同用户的设备信息，不能直接用这两个数中的任意一个替代设备总数。
练习 2：全部满足与存在
目标设备列表为空，“所有目标设备都有合法标识”与“至少有一台目标设备”分别真假？如果需求要求二者都成立，是否允许继续？
参考反馈
前者为真，后者为假，二者且起来为假。空集合没有反例，但也没有可供存在性要求使用的对象。若业务允许零目标计数，则可以返回有效的零；是否接受要依据需求，不能只凭逻辑习惯决定。
练习 3：并集怎样去掉双算
两组候选用户各有 8、5 人，其中 3 人同时出现。不同用户总数是多少？若实际交集未确认，能否直接相加得到精确人数？
参考反馈
已知交集时为 8+5−3=10。交集未知时，13 只能作为不同用户数的上界，不能当作精确值。还要确认两组各自内部已经是不同用户集合。
练习 4：重新推导扇出
四条消息使用相同快照，三位接收用户的在线设备数为 [1,2,2]。消息数、用户项数、设备数、初始任务数分别是多少？
参考反馈
依次是 4 条、3 项、5 台、20 个任务。先把不同接收方的设备数相加，再按每条消息相同的目标数相乘。20 表示计划任务，未提供实际确认信息。
练习 5：用户在线比例不能直接替代设备比例
三位接收用户的设备总数分别为 [3,1,1]，当前只有第一位用户的三台设备在线。在线用户比例、在线设备比例分别是多少？
参考反馈
在线用户为 1/3，在线设备为 3/5。一个用户多设备会改变权重，不能把 1/3 直接乘总设备数来获得本快照的确切在线设备数。若未来要按比例预测，应说明比例按用户还是按设备抽取，以及数量之间的关系。
练习 6：重试与批次
9 个任务都执行首次，只有一个任务额外试两次，总尝试数是多少？若每任务最多重试两次，最大尝试数是多少？每批最多 4 次时，能否保证只需 3 批？
参考反馈
实际给定安排是 11 次，上界是 27 次。对 11 次进行不考虑时序的装箱，至少要 3 批；能否做到取决于重试依赖和批处理限制。不能只用除法就保证实际调度批数。
练习 7：两两组合
5 条不同消息，如果不比较自己，且一对只比较一次，比较几对？若方向区分，则多少对？
参考反馈
无序为 5×4/2=10，有向为 5×4=20。如果允许自身且区分方向才是 25。需要先说明比较的对象与方向，再选择公式。
练习 8：折半与幂记号
按“向上取半，剩余不超过 1 停止”的模型，9 个候选需要几轮？0 个需要几轮？能否直接在 Go 中用 2^4 求 16？
参考反馈
9→5→3→2→1，共 4 轮；0 个按本模型直接为 0 轮，不求 log₂0。Go 的 ^ 不是乘方，不能按数学字面抄写；需要使用符合已学语法的乘法或有界循环表达倍增。
练习 9：消息条数够不够描述输入
两批各有 100 条消息，一批总正文 1000 字节，另一批 1000000 字节。若程序只检查每条是否为空，与逐字节检查全部内容，各需要关注什么规模？
参考反馈
在本章长度读取模型中，逐条检查空值主要随 n 增长；逐字节检查需要关注 B，若还包括每条的固定准备，则为 n+B 这类成本。不能把两个任务都仅按“100 条”判断为同工作量。
练习 10：给出上下界常数
证明 T(n)=3n+7 在 n≥1 时为 Θ(n)，并解释为什么它也可以写成 O(n²)。
参考反馈
n≥1 时有 3n≤3n+7≤10n，可取下界常数 3、上界常数 10、阈值 1。又因 n≤n²，它也不超过 10n²，因此 O(n²) 正确但较松。c=10 是固定常数，不能每次随 n 变化。
练习 11：只给上界能否推出紧确界
每条消息最多形成 10 个任务。有人直接写“n 条消息一定有 Θ(n) 个任务”。给一个反例，并补充一种足以支持线性下界的条件。
参考反馈
所有消息都没有目标时，任务数为 0，不具有正线性下界。若另规定每条消息至少一个、最多十个任务，就有 n≤Q≤10n，可得 Θ(n)。若讨论整体程序而非任务数，也可以用“每条消息都必须被检查一次”建立相应整体成本的下界，但必须更换并说明成本对象。
练习 12：平均查找需要哪些条件
列表长度为 10，目标保证存在且每个位置等可能，平均比较数是多少？再加入 20% 不存在，其余情况下位置等可能，结果是多少？
参考反馈
分别为 (10+1)/2=5.5 和 0.2×10+0.8×5.5=6.4。保证存在、位置等可能、找到后停止都在推导中起作用；最坏比较次数仍为 10，平均不会改变这个最大值。
练习 13：摊还有没有消除昂贵操作
教学翻倍数组从空开始插入第九个元素时，本次成本和九次总成本分别是多少？它是否推翻摊还 Θ(1)？
参考反馈
第九次复制 8 个旧元素再写入 1 个，共 9；九次总成本为 24。没有推翻，总成本仍在 N 与 3N 之间，分摊仍受常数界约束。它只说明“每次都便宜”和“任意一串操作总量线性”是不同命题。
练习 14：期望是否要求结果实际出现
一批 10 项，以概率 0.8 都只尝试一次，以概率 0.2 都尝试两次。总次数的期望与可能值是什么？能否说每批执行 12 次？
参考反馈
可能值只有 10、20，期望为 12。不能说每批 12 次，甚至这份分布下任何一批都不是 12。各任务高度相关仍可相加期望；若要计算两个任务共同成功的概率，则必须另查联合分布或独立条件。
练习 15：归纳与循环不变量
有人验证 [2]、[2,0]、[2,0,1] 三个列表求和正确，便说任何长度都正确。缺少什么？给出设备求和的不变量与终止理由。
参考反馈
缺少覆盖任意下一项的保持论证。可以声明“处理前 i 项后，累计值等于前 i 项之和”，证明初始化为 0、每次加入当前项后保持、末尾给出全和。另由未处理项数 m−i 每次减一证明终止，并保留数据合法、列表固定及无整数溢出的前提。
练习 16：完整程序与空输入
在第四节的函数中，n=0、设备列表 [-1] 应返回什么？如果只数所有消息与设备的配对，配对数为 0，是否说明函数完全没有检查工作？
参考反馈
返回 0, false，因为函数仍验证输入项，发现负设备数就拒绝。配对数为零与验证工作为零不是同一件事。类似地，普通嵌套循环即使内层次数为零，也可能保留外层推进成本；需要按实际流程选择计数口径。
完成本章后应留下什么
请为一个虚构群消息批次写一页模型，包含：对象与单位、成员和设备关系、发送者规则、快照时刻、任务与尝试公式、一个正常例子、一个零输入例子、一个能推翻过强结论的反例。
随后补两种证据：逐项累计表，以及说明规模扩大时主要成本如何增长的解释。若使用平均或概率，必须同时给出输入分布或事件假设；若使用摊还，必须说明初始状态和允许的操作序列。
下一步进入02.02 线性结构，再学 02.03 的搜索。今天先把计量对象、边界与推理工具学清，后面再比较具体的数据表示和算法。学习者自行执行的记录另存；本章所有程序输出仍是静态预期。
本章核对资料
- Algorithms 4e：算法分析：成本模型、增长与测量的关系。
- MIT 6.006，第 1 讲：正确性、输入规模与渐近界。
- MIT 6.006，第 2 讲：动态数组和摊还分析。
- MIT 数学教材：随机变量、条件概率、期望：核对概率对象、条件与加权计算。
以上材料用于知识范围与定义核对。本章的 IM 身份、工作量数字、有限 Go 计数器和分层练习均为教学设计；没有把外部教材全文作为生成知识库，也没有将模型视为上游项目的实测结论。