（b）计算模型

官官方信息技术老师·11 页·深入（追求细节与边界）·0 次浏览·3 天前

✦ （b）计算模型信息技术（b）计算模型 : 图灵机

图灵机λ演算可计算性丘奇-图灵

（b）计算模型

搞懂图灵机、λ演算为何能刻画同一个'可计算'

按空格/→ 演示下一步

1 / 11 页

全部页面点击任意一页，跳回舞台从这页播放

图灵机λ演算可计算性丘奇-图灵

（b）计算模型

搞懂图灵机、λ演算为何能刻画同一个'可计算'

1第 1 页 · （b）计算模型

: 性能测度

上页我们认识了图灵机、RAM 机这些计算模型——但光有「选手」还不够，得有一套尺子才能比出谁快谁省。这就是性能测度要做的事。

时间复杂度

计数模型执行的基本操作步数，与具体硬件速度脱钩

空间复杂度

计数占用的存储单元数（磁带格子、寄存器、内存）

渐近分析

用大 O、Θ、Ω 描述 n→∞ 时的增长量级，忽略常数因子

最坏情况为主

给出算法性能的上界，保证最差输入下也不会失控

短跑百米用时与跑道规格对应 →时间复杂度与空间复杂度

用时衡量速度（与选手体重无关），跑道长度衡量场地；都是剥离硬件后的标准指标

T(n) = O(f(n))

2第 2 页 · : 性能测度

: 问题规模

上一节我们说 T(n)、S(n) 是性能测度，但括号里的 n 到底是什么？排序时是元素个数，加密时是数字的位数，建图时是顶点数还是边数？选错尺子，再好的复杂度分析也会失真。

定义

与机器无关的输入大小抽象量，是 T(n)、S(n) 的自变量

常见选择

序列问题用元素个数 n；图问题用 n 或 n+m；数论用比特位 ⌈log₂N⌉

作用

把'输入多大'翻译成'需要多少资源'，是分析的第一步

选择影响渐近

同一问题换尺子，T(n) 形式可能变；选得不当会高估或低估

多变量边界

有些问题天然有两个规模（如图的 n 和 m），要用 T(n,m)

搬家报箱子数对应 →问题规模 n

箱子数衡量'搬多少'，n 衡量'算多大规模'；搬家费基于箱子数，T(n) 基于 n

n=\lceil\log_2(N+1)\rceil

3第 3 页 · : 问题规模

: 最坏情况

前页我们用规模 n 衡量输入大小，但同样 n 下不同输入会让算法耗时天差地别。最坏情况给的是一条「天花板」——无论输入多刁钻，运行开销都不会越过这条线。

形式化定义

在所有规模为 n 的合法输入中,算法时间/空间消耗的最大值

与输入无关

给出对任意输入都成立的上界承诺,不依赖输入分布的统计假设

典型应用

算法比较的统一基准;实时系统的硬截止时间;密码学安全性的论证起点

局限与补充

当最坏极少触发时(如哈希冲突、快速排序逆序),平均或摊还分析更贴近真实开销

大坝坝顶高度设计对应 →最坏情况复杂度

大坝按历史最大可能洪水而非平均流量设计,给的是「再大的雨也不会溃坝」的硬保证

T_{\text{worst}}(n) \;=\; \max_{|x|=n} T(x)

4第 4 页 · : 最坏情况

: 理想模型

上一页我们对比了两个算法在最坏情况下的代价。但'一次比较'到底算多贵？要公平较量算法，得先把硬件差异、系统差异抽掉——这就是理想模型要做的事。

抽象掉硬件差异

把 CPU、内存、缓存这些具体细节抽离，让算法分析独立于具体机器

操作成本统一

默认每条基本指令（算术、比较、读写）耗时相同，计为 1 个时间单位

顺序与无限内存

程序一条一条按序执行，内存视为用之不竭

两类典型模型

RAM 模型贴近现代计算机，图灵机更抽象，刻画可计算性边界

作用：公平比较

剥离硬件干扰，让算法间的差距只反映算法本身的优劣

物理课的'光滑斜面'对应 →算法分析的理想模型

都把现实中的摩擦、扰动抽掉，只保留能反映本质的规律

5第 5 页 · : 理想模型

: 图灵机

上一节说要一个'理想模型'来定义计算的边界。1936 年图灵交出的答案——图灵机——至今仍是学界最广泛接受的标尺。

七元组形式定义

Q/Σ/Γ/δ/q₀/q_accept/q_reject 七个要素完整刻画

每步确定性操作

读格 → 按δ改写 → 移头 → 切状态；绝不犹豫

无限长纸带

存储不受物理限制，是讨论'极限'的前提

通用图灵机

一台图灵机可模拟任意图灵机；现代计算机原型

丘奇-图灵论题

一切可计算函数都等价于某台图灵机（论题，非定理）

图书馆管理员按手册操作对应 →图灵机的运行机制

管理员=控制器/状态；书架格子=纸带单元；手册=转移函数δ

\delta(q, a) = (q',\, a',\, d),\; d\in\{L, R\}

6第 6 页 · : 图灵机

: 图灵机实例

上页我们看到了图灵机的抽象结构：纸带、读写头、状态、规则表。但抽象归抽象，一个具体的图灵机到底长什么样？下面看两个经典例子。

二进制加一机

从右向左扫描：遇 0 变 1 停机，遇 1 变 0 继续左传进位；最左溢出则补 1

三段等长识别

经典非上下文无关语言，需在纸带上交叉打标记才能识别；下推自动机做不到

状态转移表

(状态, 读入符号) → (新符号, 移动方向, 新状态)，完整描述这台机器的程序

停机与接受

进入接受状态 q_accept 即算出结果；无规则匹配则停机拒绝，也可能永不停留

会计按规则簿处理账本对应 →图灵机操作纸带

一次只看一格、规则书就是程序、账本无限延伸就是纸带

7第 7 页 · : 图灵机实例

: RAM模型

图灵机把每一步读写都展开，分析很严谨，却容易反复陷入“读写头怎么走”的机械细节。若只想比较算法速度，可以先把这些动作压成统一计费规则——这就是 RAM 模型。

核心定义

RAM 即随机存取机，是按址访问存储、逐条执行指令的理想化顺序机。

随机访问

“随机”不是随便选：程序可按地址直接取出一个数据单元，抽象访问代价与位置无关。

统一计费

经典模型把整数算术、比较、读写等基本操作按常数时间计费。

现实边界

它不刻画缓存、流水线与时钟；一旦计入字长或位操作，复杂度可能出现对数因子变化。

典型应用

把伪代码转成操作次数或递推式，比较排序、搜索、遍历等算法的渐近增长率。

编号储物柜对应 →RAM模型

程序给地址，就像管理员报柜号；模型规定直接取物并统一计费，忽略真实移动与排队。

8第 8 页 · : RAM模型

: RAM实例

上一页给出了 RAM 的规则，但没有说明一次分析从哪里开始。固定一个算法，再放入具体输入，就得到可逐步跟踪的 RAM 实例。

实例

固定算法 A 与输入 x 后，RAM 的一次运行过程

状态

程序计数器、寄存器、存储内容及地址随指令逐步变化

同机异例

同一程序面对不同 x，执行路径、读写位置和操作数可能不同

计数口径

基本 RAM 中各基本操作按单位代价计入 T_A(x)

最坏与用途

A 对 x 停机时，对长度 n 的输入取最大值，用于比较算法增长

按同一菜谱做一道菜对应 →固定算法在 RAM 上运行

菜谱相当于程序，食材和用量相当于输入，具体烹饪过程对应实例及代价

T_A(x)=\text{基本操作数},\quad W_A(n)=\max_{|x|=n,\;A\text{ 停机}}T_A(x)

9第 9 页 · : RAM实例

本节要点

✓性能必须依附模型——脱离图灵机或RAM谈快慢无意义
✓大O刻画增长趋势，常数与底层模型共同决定实际耗时
✓最坏情况是算法的承诺上限，不代表典型表现
✓图灵机回答「能不能算」，RAM回答「算多快」

延伸主题：复杂度类与P、NP问题摊还分析与平均复杂度真实硬件对模型假设的偏离

10第 10 页 · 本节要点

课后思考

三个开放问题，先自己琢磨 5 分钟再翻参考答案。

1为什么分析算法时要用图灵机、RAM 这类理想模型，而不是直接用真实计算机？

参考答案真实机器太复杂——缓存、流水线、操作系统都会干扰。理想模型把这些细节剥离，只保留“顺序执行、每步代价为 1”的核心抽象，让我们能专心度量算法本身的思想代价，而不是机器的工程噪声。

2若 RAM 程序在规模 n 上跑 T(n) 步，能直接断言它在真实计算机上也是 O(T(n)) 吗？什么因素会让两者脱节？

参考答案结论的“形状”通常成立，但常数因子会被真实硬件扭曲。RAM 假设每条指令代价恒为 1，真实机器却有缓存命中/未命中、分支预测、并行度等差异——同一算法在不同机器上可能差出几十倍。

3图灵机与 RAM 在时间上多项式等价，但若改问空间复杂度，这种等价还成立吗？

参考答案需要更细致论证。时间维度的等价靠“一格移动对应一次寄存器访问”的代价匹配；空间维度上，多带图灵机与 RAM 的开销并不同步，对数空间等价有专门定理，不能直接套用时间结论。

11第 11 页 · 课后思考