通道一的机制可以一句话说完:
旧 D 在旧 E 上仍然做得出来,但随着 E 的规模上升,代价增长到不可接受;
新 S 是一次表示压缩,它把代价降阶,并保证旧 D 的输出可以从新表示中恢
复。
要点在“仍然做得出来”。这是通道一与通道三的分界:通道一里旧方法没有失败,只是变得昂贵;通道三里旧方法根本给不出对象。混淆这两者,是既有文献里最常见的一处错误,本编第十九章将纠正一次具体的误判。
把第一编的概念发生链按代价重排,通道一的签名立刻显形。设规模参数为 n。
旧D 任务 旧代价 新S 新代价 性质
逐一记号 记录数量 N Θ(N) 个符号 位值制 Θ(log N) 个 指数压缩
符号
数数 求 k 组已知 Θ(N),N 为 加法 Θ(k·log N) 指数压缩
数量之和 总数
加法 a 重复 n 次 Θ(n) 次运算 乘法 Θ(1) 符号长 指数压缩
度
乘法 a 自乘 n 次 Θ(n) 次乘法 幂 Θ(1) 符号长 指数压缩
度
通分 两个分数比 求最小公倍 小数 逐位对齐 局部化
大小 数 Θ(位数)
幂 由 aˣ=b 求 x 无直接算 对数 乘法群 → 局部化
法,试探 加法群
有限差分 求瞬时变化 不可达(只 微分 一次求导 见第二十章
率 能逼近)前四行是同一件事的四次重演:把“重复”折叠成“参数”。逐一记号把 N 个记号折成 log N 位;加法把“重新数一遍”折成“取已有结果相加”;乘法把“重复加”折成“因子与次数”;幂把“重复乘”折成“底与指数”。每一次折叠都把线性代价降为对数代价或常数符号长度。
第五、六行不同:小数与对数并没有把代价降阶,它们做的是另一件事——把一个不好算的运算搬到一个它好算的表示里。通分的困难不在于规模,在于最小公倍数依赖两个分母的算术关系;小数把这一依赖去掉,代价变成纯位数。对数把乘法搬进加法。这一类本章称为局部化型压缩,第十七章会说明它为什么必然出现。
第七行是难判例,留到第二十章处理。
据此可以写出通道一的判定签名,三条同时满足才算通道一:
签名 A1(代价降阶). 存在规模参数 n 与任务族,使旧 D 的代价 C(n) 与新 S
的代价 c(n) 满足 c(n) = o(C(n));或旧运算在新表示下由非局部变为局部。
签名 A2(可恢复). 旧 D 的全部输出可由新 S 在不高于 O(c(n)) 的代价内恢
复。新 S 没有增加可表达的对象,只是把同一批对象表示得更短。
签名 A3(旧 D 未失败). 在新 S 出现之前,旧 D 对每个有限实例都给得出正
确答案。
A2 是这条签名的判错开关。 它要求“表达域不变”。若新 S 让原本表示不了的对象变得可表示,则 A2 为假,该次发生不是通道一——不论它看上去多么像“旧办法太麻烦了”。
第十九章将用这一条推翻一处流行的归属。
小学到初中的绝大部分内容都落在通道一:位值制、四则、竖式、九九表、约分、小数、指数律、对数律。这解释了一个长期被误解的现象——这些内容之所以能被“训练”出来,正是因为它们是压缩。压缩有明确的效率指标,效率可以练。
同时这也划出了训练的边界:通道二与通道三的内容练不出来。一个学生把分数运算练到极熟,不会因此更接近理解“为什么需要分数”,因为分数不走通道一(第十九章)。把三条通道的内容用同一套办法教,是当前数学教育里一处结构性的错配。这一判断可以被检验:若把分数按扩张通道教(从“除法在整数上不封闭”入手)而非按压缩通道教(从“分东西太麻烦”入手),理解指标应有可测的差异。这是本编留给教育研究的一个可证伪预言。