算法 vs 程序:
- 算法是抽象的数学对象，独立于任何编程语言
- 程序是算法在特定语言中的具体实现
- 程序可能不终止（如操作系统），但算法必须终止

Knuth 的形式化方法:
用计算序列（computational sequence）来定义算法
Q = 计算步骤的集合
I = 输入域
Ω = 输出域
f = 从 Q×Q 的转换函数（每一步的计算规则）

MIX 的基本结构:
- 字（Word）: 5 个字节 + 符号位
- 字节（Byte）: 可配置大小（通常 6 或 8 bit，可表示 64 或 256 个值）
- 累加器 rA: 一个带符号的字
- 扩展累加器 rX: 一个带符号的字（用于乘除法）
- 索引寄存器 rI1-rI6: 6 个寄存器
- 跳转寄存器 rJ: 保存返回地址
- 比较标志: LESS, EQUAL, GREATER
- 溢出触发器: 算术溢出标志

内存: M 个字的存储空间（M 的大小不限）

指令格式:
┌──────┬──┬──┬──────┐
│ ADDR │ IX│ C  │ OP │
│(2字节)│(1B)│(1B)│(1B)│
└──────┴──┴──┴──────┘

ADDR: 地址字段（可以是表达式如 1000,2:3）
IX: 索引寄存器选择（0=不使用,1-6=使用 rI1-rI6）
C: 修改符（指定使用字的哪些部分）
OP: 操作码

证明 P(n) 对所有 n ≥ n₀ 成立:
1. 基础步骤: 证明 P(n₀) 成立
2. 归纳步骤: 假设 P(k) 成立（归纳假设），证明 P(k+1) 成立

示例: 证明 1 + 2 + ... + n = n(n+1)/2
基础: n=1, 左边=1, 右边=1×2/2=1 ✓
归纳: 假设 1+2+...+k = k(k+1)/2
      1+2+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 ✓

证明 P(n) 对所有 n ≥ n₀ 成立:
1. 基础步骤: 证明 P(n₀) 成立
2. 归纳步骤: 假设 P(n₀), P(n₀+1), ..., P(k) 全部成立，证明 P(k+1) 成立

示例: 证明每个整数 n ≥ 2 可以分解为素数的乘积
基础: n=2, 2 是素数 ✓
归纳: 假设 2,3,...,k 都可以分解
      对于 k+1:
      - 如果 k+1 是素数 → 完成
      - 如果 k+1 = a×b (1 < a,b < k+1) → 由归纳假设，a 和 b 都可以分解
        → k+1 也可以分解 ✓

大 O 记号:
T(n) = O(f(n)) 当且仅当存在常数 c, n₀ 使得 T(n) ≤ c·f(n) 对所有 n ≥ n₀

常见复杂度:
O(1)    < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Knuth 强调的分析方法:
1. 精确分析: 计算精确的执行步数（包含常数因子）
2. 渐近分析: 只关注增长趋势（大 O 记号）
3. 平均情况分析: 对所有可能输入取平均
4. 最坏情况分析: 对所有可能输入取最大值

Knuth 更倾向于精确分析，因为常数因子在实际中很重要

欧几里得算法（求最大公约数）:
算法 E (Euclid's algorithm). 给定两个正整数 m 和 n，求它们的最大公约数。

E1. [求余] 用 n 除 m，令 r 为余数。（0 ≤ r < n）
E2. [r=0?] 如果 r = 0，算法终止，n 就是答案。
E3. [n←m] 将 n 的值赋给 m。
E4. [m←r] 将 r 的值赋给 n。返回 E1。

MIX 实现:
ORIG 3000
START  LDA    M        rA ← m
       DIV    N        rA ← ⌊m/n⌋, rX ← m mod n
       STX    R        r ← m mod n
       JXZ    DONE     if r = 0, goto DONE
       LDN    N        n ← m (注意: LDN 加载负值)
       LDA    N
       CHS             取反得到 m
       STA    M        m ← n (旧)
       LDA    R
       STA    N        n ← r
       JMP    START    返回 E1
DONE   ...             n 是答案

正确性证明:
关键不变量: gcd(m, n) = gcd(m mod n, n)
证明: 设 m = qn + r
      如果 d | m 且 d | n → d | (m - qn) = r → d | r
      如果 d | n 且 d | r → d | (qn + r) = m → d | m
      所以 m 和 n 的公因数集合 = n 和 r 的公因数集合
      → gcd(m, n) = gcd(n, r)

终止性证明:
每次迭代 r < n，所以 n 严格递减
n 是正整数，有限步后必然达到 r = 0

复杂度分析:
Lamé 定理: 欧几里得算法的步数不超过 n 的十进制位数的 5 倍
即步数 ≤ 5 × log₁₀(n) ≈ 1.67 × log₂(n)
平均步数 ≈ (12 ln 2 / π²) × ln(n) ≈ 0.843 × ln(n)