--- tags: [算法分析与设计] abstract: 算法定义、插入排序、循环不变式与正确性证明 finished: false 上一篇: [[计算机系/算法分析与设计/00 算法学习导论|上一篇]] 下一篇: [[计算机系/算法分析与设计/02 伪代码与算法表达|下一篇]] 返回目录: [[计算机系/算法分析与设计/算法分析|算法分析与设计学习指南]] 前置知识: [[计算机系/算法分析与设计/00 算法学习导论|前置知识]] --- # 算法入门与正确性证明 ## 算法入门 算法是对特定问题求解步骤的一种描述，是若干个指令的有穷序列，满足性质/特征： 1. 0或多个输入 2. 1或多个输出 3. 有穷性 每条指令的执行次数是有限的、执行每条指令的时间也是有限的 4. 确定性 组成算法的每条指令是清晰的、无歧义的 5. 可行性 因此算法具有正确性、可读性、健壮性、（可使用性）、效率与低存储量需求 一个算法是由控制结构（顺序、分支和循环3种）和原操作（固有数据类型的操作）构成的。（或者说每一行代码所运行的操作） 从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间复杂度 算法的效率 1. 事后统计的方法 2. 事前估计的方法 问题规模n，输入序列I，算法本身A 书写程序的语言 编译程序所产生的机器代码质量 机器执行指令的速度 算法的正确性 不正确的算法不是都没用 1. 近似 2. 模拟 找不到精确解就找一个近似的解 可计算性 理论上判断什么问题可以给出算法利用计算机求解，什么问题不可以，属于“可计算性理论” 研究的问题 比如“停机问题”就是不可计算的 可计算理论认为可计算的问题，都有求解的算法，这样的算法不是唯一的 ### 插入排序 排序问题 输入:n个数\ 输出：输入序列的一个排列(重新排序) $,$ 使得 $a'1≤a'2...≤a'n$ 插入排序算法思想: **“扑克牌理牌”思想**。 你可以想象自己在打扑克牌时，如何将新摸到的一张牌插入到手中已经排好序的牌里：你会从右往左（或从左往右）扫描手中的牌，找到合适的位置，把这张新牌插进去，并把比它大的牌往后挪。 伪代码： INSERTION-SORT(A) ``` for j<-2 to length[A] do key <-A[j] Insert A[j] into the sorted sequence A[1...j-1]. i<-j-1 while i>0 and A[i] >key do A[i+1] <-A[i] i<-i-1 A[i+1]<-key ``` ^INSERTION ### 循环不变式与插入排序的正确性 **(Loop invariants and the correctness of insertion sort)** 在循环内及循环结束的时候都成立的表达式 用于证明算法 的正确性 基本思想： > 如果在循环的每一步，这个式子都是正确的，那么循环结束后，这个式子也正确，并得到了期望的结果。 三条重要性质： - **初始化(Initialization)**：循环的第一次迭代之前，循环不变式为真。 - 作用：证明归纳基础成立。 - **保持(Maintenance)**：循环过程中每次迭代前后，循环不变式为真，布尔性质保持不变。（如果在循环的某一次迭代开始之前它是正确的，那么在下一次迭代开始之前，它也应该保持正确） - 作用：证明“如果这轮真，下轮也真”。 - **终止(Termination)**：循环终止时，不变式返回正确的结果，并且能够证明算法的正确性。 - 作用：把不变式变成最终结论。 评：除了插入排序（左边排好序右边未排序），典型的还有二分查找（if判断中左边check为true右边check为false或者左边check为false右边check为true），这些算法都具有明显的二段性。 插入排序的算法正确性 ![[01 算法入门与正确性证明#^INSERTION]] 在外层for循环（循环变量为j）的每一轮迭代开始，包含元素A[1...j-1]的子数组已排好序 - 初始化:j=2,子数组只包含一个元素A[1]，显然有序 - 保持：在外层for循环的循环体中，要将A[j-1],A[j-2]..A[j-3]等元素向右移一个位置，直到找到A[j]的适当位置，此时将A[J]的值插入，此时A[1..j]也是有序的。 - 终止：当j大于n时(j=n+1)，外层for循环结束，将j替换成n+1，子数组为A[1..n]，根据保持性A[1...n]有序，即所需输出 求数组A[1:n]的元素和。描述程序的循环不变量(loop invariant) 初始化，保持，终止 ``` SUM-ARRAY(A,n) sum=0 for i=1 to n sum=sum+A[i] return sum ``` 循环不变量：sum记录了A[1:i]的元素和 - 初始化sum=0;i=1 - 保持: sum=sum+A[i] - 终止:i=n+1,返回sum ## 数学归纳法整理 数学归纳法是一种证明与正整数有关的命题的常用方法。常见形式有**第一数学归纳法**和**第二数学归纳法**（也叫强归纳法）。 ## 四、第一数学归纳法 ### 1. 基本步骤 1. **归纳基础**：验证 n=1 时命题 P(1) 成立。 2. **归纳假设**：假设 n=k 时命题 P(k) 成立。 3. **归纳递推**：证明 n=k+1 时命题 P(k+1) 也成立。 则命题 P(n) 对一切正整数 n 都成立。 ### 2. 理解 如果假设 P(k) 成立，能推出 P(k+1) 成立，那么就有： $$ P(1)\to P(2),\quad P(2)\to P(3),\quad P(3)\to P(4),\quad \cdots $$ 由于 P(1) 成立，于是 P(2) 成立； 由于 P(2) 成立，于是 P(3) 成立； 依此类推，所有正整数 n 都成立。 ### 3. 例子：证明 $$ 1+2+3+\cdots+n=\frac{n(n+1)}{2} $$ **证明：** **① 当 n=1 时：** 左边 =1，右边 =1×2/2=1，成立。 **② 假设 n=k 时成立，即：** $$ 1+2+\cdots+k=\frac{k(k+1)}{2} $$ **③ 证明 n=k+1 时也成立：** $$ \begin{aligned} 1+2+\cdots+k+(k+1) &=\frac{k(k+1)}{2}+(k+1)\\ &=\frac{k(k+1)+2(k+1)}{2}\\ &=\frac{(k+1)(k+2)}{2} \end{aligned} $$ 这正是 n=k+1 时的公式。 所以，对一切正整数 n，命题成立。 --- ## 五、第二数学归纳法（强归纳法） ### 1. 基本步骤 1. **归纳基础**：验证 n=1（有时需要验证 n=1,2）时命题成立。 2. **归纳假设**：假设对于所有 n 注意：第二数学归纳法不一定必须验证 \(n=1\) 和 \(n=2\)，具体验证几个基础情形，取决于递推关系需要用到前几项。例如若递推关系只用到前一项，验证 \(n=1\) 即可；若用到前两项，则通常验证 \(n=1,2\)。 ## 六、两种归纳法对比 | 比较项 | 第一数学归纳法 | 第二数学归纳法 | | --- | --- | --- | | 归纳假设 | 假设 n=k 时成立 | 假设所有 n 注意：第二数学归纳法不一定必须验证 n=1 和 n=2，具体验证几个基础情形，取决于递推关系需要用到前几项。例如若递推关系只用到前一项，验证 n=1 即可；若用到前两项，则通常验证 n=1,2。 #### 类比数学归纳法 循环不变式的三条性质，本质上是数学归纳法在算法正确性证明中的具体化。 | 循环不变式 | 数学归纳法 | | --- | --- | | 初始化 | 归纳基础 | | 保持 | 归纳递推 | | 终止 | 归纳结论 + 循环结束条件 ⇒ 算法目标 | 算法和数据结构的联系与区别 联系：数据结构是算法设计的基础。算法的操作对象是数据结构，在设计算法时，要构建适合这种算法的数据结构，数据结构设计主要选择数据的存储方式，如求解问题中的数据采用数组存储还是用链表存储。算法设计就是在选定的存储结构上设计一个满足要求的算法。 数据结构关注的时数据的逻辑结构、存储结构和基本操作，而算法 更多是关注如何在数据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的逻辑基础。 ```mermaid graph TD A[分析求解问题] --> B[选择数据结构和算法设计策略] B -->C[描述算法] C -->D[证明算法正确性] D -->E[算法分析] ``` ## 核心定理与证明 > [!theorem] 插入排序正确性 > 对任意长度为 $n$ 的数组，`INSERTION-SORT` 终止时输出按非降序排列的原数组元素。 > ^thm-insertion-sort-correct > [!proof]- 证明（循环不变式） > 取外层循环每轮开始前的不变式：子数组 $A[1..j-1]$ 已按非降序排列，且包含原数组前 $j-1$ 个元素。初始化时 $j=2$，单元素数组有序。保持性：内层循环把所有大于 `key` 的元素右移，随后把 `key` 放入第一个不大于它的位置，因此 $A[1..j]$ 仍有序且元素集合不变。终止时 $j=n+1$，不变式给出 $A[1..n]$ 有序，且循环只做有限次递增迭代，故算法终止并正确。 > [!theorem] 插入排序最坏情况复杂度 > 逆序输入时，插入排序执行 $\Theta(n^2)$ 次基本比较/移动操作；已排序输入时为 $\Theta(n)$。 > ^thm-insertion-sort-complexity > [!proof]- 证明 > 逆序输入时，第 $j$ 轮需要移动 $j-1$ 个元素，总代价为 $\sum_{j=2}^{n}(j-1)=n(n-1)/2=\Theta(n^2)$。已排序输入时每轮只做一次成功比较和常数次赋值，总代价为 $\sum_{j=2}^{n}O(1)=\Theta(n)$。