循环不变量

用于证明迭代算法

例题：用循环不变量证明选择排序正确性

• 循环不变量：在第\(j\)次迭代执行前，\(A[1,2,...,j-1]\)已经有序
• 初始步：在第一次迭代之前，已排序的子序列为空，因此循环不变量成立。
• 归纳步：假设在第\(j=k\)个迭代前，\(A[1,2,..,k-1]\)有序。当执行迭代\(j=k\)时，从\(A[k,,,n]\)中选出最小的元素放在已排序序列的末尾，则在第\(k\)次迭代后，\(A[1,2,...,k]\)将包含第k个最小元素并且保证\(A[k-1]<=A[k]\)，因此\(A[1,2,...,k]\)有序。
• 终止步：当\(j=n+1\)时，循环终止，此时\(A[1,2,...,n]\)有序，算法正确。

渐进符号

1. 同阶、渐进紧界

   • 定义

   

   ​

   • 证明

     • 定义

       

     • 极限

       

2. 低阶、渐进上界

   • 定义

     

     

   • 证明

     • 定义

     • 极限

       

3. 高阶、渐进下界

   • 定义

     

     

   • 证明

     • 定义

     • 极限

       

4. 例题

   • 相加取大

     

   • 定理2.1

     

     

算法分析方法

概率分析

• 优点：概率分析基于概率论和随机性质，可以在平均情况下评估算法的性能。它考虑了输入的可能分布情况，对于涉及随机性的算法特别有用。

• 缺点：概率分析通常需要对输入的概率分布进行假设，并且在某些情况下可能难以准确估计概率。此外，它可能忽略最坏情况下的性能。

• 例子

  • 线性搜索

    

  • 插入排序

    

  • 聘用秘书

    

分摊分析

• 优点：不需要复杂的概率分析且更符合实际情况，保证了最坏情形下每个运算的平均性能。

• 缺点：分摊分析假设每个操作的开销都是均摊到所有操作中的，但实际情况可能有所不同。对于特定输入，某些操作的实际开销可能会超过平均开销。

• 方法

  • 合计方法：求出每一次运算的费用，加起来得到总费用关于\(n\)的表达式\(T(n)\)，则分摊费用就是\(T(n)/n\)

  • 记账方法：想出来要给每次运算分配的费用是多少，列出运算序列、分摊费用、实际费用、存款这四个数列，发现存款始终非负，则分摊费用就是想出来的那个

  • 势能方法

  • 重要不等式

    \(\sum_{j=0}^{lgn}2^j=2n-1\)

• 例子

  • multipop

    

  • 二进制累加

    

实验分析

• 优点：简单实用
• 缺点：容易受所选测试实例、计算模型、实验参数等的影响

递归

例子

1. 计算\(2^k\)问题

   

   

   

2. 汉诺塔问题

   

   

   求时间复杂度就是把\(T(n)\)解出来，这里\(T(n)=O(2^n)\)

3. 选择排序

   

   

   

4. 排列问题

   方法一：

   

   方法二：

   

   时间复杂度递推关系式：

   

设计原则

公式法解递归方程

这里的结果是同阶（渐进紧界）的，用\(\Theta\)符号

动态规划

与分治的关系

装配线调度

• 求解思路

  1. 先分析出最优子结构性质是什么

     

     

  2. 然后说根据这个可以构造出状态转移方程

     

• 为什么能DP

  • 证明最优子结构性质

    

  • 递归方程

    

    

  • 说明重叠子问题

    

• 伪代码

  

• 时间复杂度分析

  

矩阵链乘法

1. 问题描述

   

2. 最优子结构性质

   

3. 状态转移方程（区间DP）

   

4. 填表

   
   \(i>j\)，即对角线以下不填

   \(i = j\)，副对角线填0

   之后沿着平行对角线方向从下往上填

最长公共子序列

1. 问题描述

   

2. 最优子结构性质

   

3. 状态转移方程

   

4. 填表

   

   例子：

   

0/1背包

1. 问题描述

   

2. 最优子结构性质

   

3. 状态转移方程

   

4. 填表

   

   

   例子

   

做题

1. 求解思路

   • 最优子结构性质是什么
     • 原问题的一个最优解要用到哪些子问题
     • 包含在原问题里的这些子问题的解是它们的最优解
   • 由最优子结构性质，描述状态转移方程的构造思路

2. 为什么能DP

   • 证明最优子结构性质

     • 定义：原问题的最优解中所包含的子问题的解是子问题的最优解

     • 证明方法

       反证法

       已知当前解是原问题的最优解。假定当前解中的\(p\)不是子问题的最优解，则子问题存在最优解\(p^{'}\)，将\(p^{'}\)替换\(p\)，则可以得到原问题的更优解，矛盾。故假设不成立，则\(p\)就是子问题的最优解。

   • 说明重叠子问题

     • 定义：重复出现的子问题
     • 从递归方程可知，划分后的子问题都需要求解相同的“子子问题”

   • 写状态转移方程

3. 伪代码

4. 时间复杂度分析

回溯和分支限界