JZTXT

知识点

发布时间 2023-06-28 15:41:04作者: sakuraLGGM

循环不变量

用于证明迭代算法

image-20230627092857590

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

  • 循环不变量：在第\(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. 同阶、渐进紧界

    • 定义

    image-20230627100937706

    ​ image-20230627101043495

    • 证明

      • 定义

        image-20230627101149026

      • 极限

        image-20230627101213908

  2. 低阶、渐进上界

    • 定义

      image-20230627101332870

      image-20230627101354837

    • 证明

      • 定义

      • 极限

        image-20230627101435130

  3. 高阶、渐进下界

    • 定义

      image-20230627101522567

      image-20230627101531957

    • 证明

      • 定义

      • 极限

        image-20230627101617665

  4. 例题

    • 相加取大

      image-20230627101656163

    • 定理2.1

      image-20230627101856039

      image-20230627101902976

算法分析方法

概率分析

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

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

  • 例子

    • 线性搜索

      image-20230627102755552

    • 插入排序

      image-20230627102848555

    • 聘用秘书

      image-20230627102920041

分摊分析

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

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

  • 方法

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

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

    • 势能方法

    • 重要不等式

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

  • 例子

    • multipop

      image-20230627104056368

    • 二进制累加

      image-20230627104210131

实验分析

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

递归

例子

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

    image-20230627112049243

    image-20230627113640765

    image-20230627112104264

  2. 汉诺塔问题

    image-20230627112433191

    image-20230627112158689

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

  3. 选择排序

    image-20230627113734222

    image-20230627112700814

    image-20230627113109499

  4. 排列问题

    方法一：

    image-20230627114934191

    方法二：

    image-20230627115749799

    时间复杂度递推关系式：

    image-20230627115934256

设计原则

image-20230627120202030

公式法解递归方程

image-20230627120601774

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

动态规划

与分治的关系

image-20230627122437271

装配线调度

  • 求解思路

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

      image-20230627160857502

      image-20230627160927852

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

      image-20230627160019522

  • 为什么能DP

    • 证明最优子结构性质

      image-20230627161010275

    • 递归方程

      image-20230627155532463

      image-20230627155548911

    • 说明重叠子问题

      image-20230627155506474

  • 伪代码

    image-20230627155642272

  • 时间复杂度分析

    image-20230627155746145

矩阵链乘法

  1. 问题描述

    image-20230627163953190

  2. 最优子结构性质

    image-20230627164043397

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

    image-20230627164128842

  4. 填表

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

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

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

最长公共子序列

  1. 问题描述

    image-20230627171055381

  2. 最优子结构性质

    image-20230627171130013

  3. 状态转移方程

    image-20230627171159511

  4. 填表

    image-20230627171217651

    例子：

    image-20230627171310491

0/1背包

  1. 问题描述

    image-20230627172214975

  2. 最优子结构性质

    image-20230627173209926

  3. 状态转移方程

    image-20230627173250235

  4. 填表

    image-20230627173313437

    image-20230627173605140

    例子

    image-20230627173624111

做题

  1. 求解思路

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

  2. 为什么能DP

    • 证明最优子结构性质

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

      • 证明方法

        反证法

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

    • 说明重叠子问题

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

    • 写状态转移方程

  3. 伪代码

  4. 时间复杂度分析

回溯和分支限界