分析算法

循环不变式 (Loop Invariant)

循环不变式是用于证明算法（特别是循环类算法）正确性的重要工具。它是一个逻辑断言，在循环的每一次迭代前后都保持为真。

为了证明算法的正确性，我们需要验证关于循环不变式的三个性质：

1. 初始化 (Initialization)： 在循环的第一次迭代开始之前，循环不变式为真。这通常可以被视为数学归纳法的基本情况（Base case）。
2. 保持 (Maintenance)： 如果在某次迭代开始之前循环不变式为真，那么在下一次迭代开始之前，它依然为真。这对应于数学归纳法的归纳步骤。
3. 终止 (Termination)： 当循环结束时，不变式提供了一个有用的性质，该性质有助于证明算法是正确的。

示例（插入排序）：

在 for j = 2 to A.length 的循环开始前，子数组 A[1..j-1] 包含了原数组中前 j-1 个元素，且已按序排列。

伪代码 (Pseudocode)

伪代码是一种非正式的高级语言，用于描述算法的逻辑结构，忽略了具体的语法细节（如变量声明、内存管理），以便人类阅读和理解。

通用约定：

• 缩进：表示块结构（Block structure），代替了 {} 或 begin/end。
• 控制流：使用 if、else、while、for、repeat-until 等常见关键字。
• 赋值：通常使用 ← 或 = 表示赋值操作（例如 x ← y）。
• 变量：通常是局部变量，除非显式声明为全局。
• 数组访问：使用 A[i] 表示数组 $A$ 的第 $i$ 个元素。
• 对象属性：使用 attribute[x] 或 x.attribute（例如 length[A] 或 A.length）。
• 注释：通常用 // 或 ▷ 表示。

示例片段：

INSERTION-SORT(A)
1  for j ← 2 to A.length
2      key ← A[j]
3      // 将 A[j] 插入到已排序序列 A[1..j-1]
4      i ← j - 1
5      while i > 0 and A[i] > key
6          A[i + 1] ← A[i]
7          i ← i - 1
8      A[i + 1] ← key

执行时间 (Execution Time)

执行时间是指算法解决问题所需的时间，通常表示为输入规模 $n$ 的函数。

1. 输入规模 ($n$)：
   • 对于排序问题，$n$ 是数组中的元素个数。
   • 对于图算法，$n$ 可能是顶点数或边数。
   • 对于整数运算，$n$ 可能是二进制表示的位数。
2. 计算模型 (RAM 模型)：
   • 假设指令（加、减、乘、除、数据移动、控制流）按顺序执行。
   • 每条简单指令执行需常量时间 $c$。
3. 分析类型：
   • 最坏情况 (Worst-case)：对任意规模 $n$ 的输入，算法运行时间的最长可能时间。这是最常用的分析指标，因为它提供了时间的上界保证。
   • 平均情况 (Average-case)：期望的运行时间，通常基于输入数据的概率分布假设。
   • 最好情况 (Best-case)：通常用处不大，但在特定场景下（如快速排序的最好情况分析）有参考价值。
4. 渐进符号：
   • $\mathrm{\Theta }(n)$：紧确界（既是上界又是下界）。
   • $O(n)$：渐进上界（关注最坏情况）。
   • $\mathrm{\Omega }(n)$：渐进下界。

习题

1. 指出竖式除法（除数是整数）的循环不变式

背景设定： 假设我们要计算 $A÷B$。

• $A$ 是被除数，由数字序列 $A[n-1\dots 0]$ 组成（或者 $A[1\dots n]$，视索引习惯而定，这里假设从高位到低位处理）。
• $B$ 是除数（整数）。
• $Q$ 是最终的商。
• $R$ 是最终的余数。
• 在算法过程中，$q$ 是当前生成的商，$r$ 是当前的部分余数。

竖式除法过程回顾： 我们在每一轮循环中，从被除数 $A$ 的高位拉下一位数字（Drop down），拼接到当前余数 $r$ 的末尾，然后尝试除以 $B$，更新商的当前位和新的余数。

循环不变式：

假设我们在第 $i$ 次迭代（处理被除数 $A$ 的第 $i$ 位数字，设该位为 $d_i$）：

在处理第 $i$ 位数字之前，当前累积的商 $q$ 和当前余数 $r$ 满足以下关系：

$$A_{prefix}=q\times B+r$$

其中：

• $A_{prefix}$ 是被除数 $A$ 已经被处理过的前缀部分（即从最高位到第 $i-1$ 位组成的整数）。
• $0\le r<B$ （余数必须始终小于除数）。

证明（验证三要素）

为了更清晰地说明，假设被除数 $A$ 的十进制表示为 $d_k{d}_{k-1}\dots d_0$。我们从高位 $k$ 开始循环到 $0$。

1. 初始化 (Initialization)：

   • 在循环开始前，我们还没有处理任何数字。
   • $A_{prefix}$ 是空的，数值为 0。
   • 我们初始化 $q=0$, $r=0$。
   • 代入公式：$0=0\times B+0$，且 $0\le 0<B$。
   • 成立。

2. 保持 (Maintenance)：

   • 假设在某次迭代开始前，性质 $A_{old\mathrm{\_}prefix}=q_{old}\times B+r_{old}$ 成立。
   • 循环操作：
     1. 落下下一位数字 $d$。新的被除数前缀值变为了 $A_{new\mathrm{\_}prefix}=A_{old\mathrm{\_}prefix}\times 10+d$。
     2. 构造新的被除部分：$temp=r_{old}\times 10+d$。
     3. 计算商的当前位：$digit=\lfloor temp/B\rfloor$。
     4. 更新余数：$r_{new}=temp\mathrm{mod}B$。
     5. 更新总商：$q_{new}=q_{old}\times 10+digit$。
   • 验证： 我们需要证明 $A_{new\mathrm{\_}prefix}=q_{new}\times B+r_{new}$。$$\begin{array}{rl}{q}_{new}\times B+r_{new}& =(q_{old}\times 10+digit)\times B+(temp-digit\times B)\\ & =10\cdot q_{old}\cdot B+digit\cdot B+temp-digit\cdot B\\ & =10\cdot q_{old}\cdot B+temp\\ & =10\cdot q_{old}\cdot B+(r_{old}\times 10+d)\\ & =10\cdot (q_{old}\cdot B+r_{old})+d\end{array}$$根据归纳假设，$q_{old}\cdot B+r_{old}=A_{old\mathrm{\_}prefix}$。 所以上式 $=10\cdot A_{old\mathrm{\_}prefix}+d$，这正是 $A_{new\mathrm{\_}prefix}$。
   • 成立。

3. 终止 (Termination)：

   • 当循环结束时，所有的位数都已处理完毕，$A_{prefix}$ 等于完整的被除数 $A$。
   • 此时，$q$ 变成了最终的商 $Q$，$r$ 变成了最终的余数 $R$。
   • 根据不变式：$A=Q\times B+R$，且 $0\le R<B$。
   • 这正是除法算法正确性的定义。
   • 成立。