分析算法

循环不变式 (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)$：渐进下界。

习题

#20201

⚡1⏳2

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

#20202

⚡1⏳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{aligned} 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{aligned} $\mathrm{根}\mathrm{据}\mathrm{归}\mathrm{纳}\mathrm{假}\mathrm{设}，$q_{old} \cdot B + r_{old} = A_{old_prefix}$。 所以上式 $=10\cdot A_{old\mathrm{\_}prefix}+d$，这正是 $A_{new\mathrm{\_}prefix}$。 * 成立。

#20203

⚡1⏳2

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