2022Fall_算法导论笔记

目录

  1. 1. 算法复习
    1. 1.1. 递归/分治策略/求解递归式
      1. 1.1.1. 渐进记号
      2. 1.1.2. 求解递归式
        1. 1.1.2.1. 代入法
        2. 1.1.2.2. 递归树法
        3. 1.1.2.3. 主方法
        4. 1.1.2.4. 证明: 数学归纳法
      3. 1.1.3. 归并排序
      4. 1.1.4. 快速排序
    2. 1.2. 二叉树/红黑树/区间树
      1. 1.2.1. 红黑树
      2. 1.2.2. 数据结构扩张
      3. 1.2.3. 区间树
    3. 1.3. 动态规划/贪心算法
      1. 1.3.1. 动态规划
        1. 1.3.1.1. 装配线问题
        2. 1.3.1.2. 矩阵链乘法
        3. 1.3.1.3. 公共最长子序列LCS
      2. 1.3.2. 贪心算法
        1. 1.3.2.1. 活动选择问题
        2. 1.3.2.2. 背包问题
        3. 1.3.2.3. Huffman编码
        4. 1.3.2.4. 胚理论
    4. 1.4. 平摊分析(势函数法)
      1. 1.4.0.1. 栈操作
      2. 1.4.0.2. 二进制计数器
      3. 1.4.0.3. 动态表
  2. 1.5. 二项堆/FIB堆
    1. 1.5.1. 二项树
    2. 1.5.2. 二项堆
    3. 1.5.3. FIB堆
  3. 1.6. 最大流/最小切

算法导论3E

算法复习

往年试题:
CLRS1
CLRS2

考试题型:

  • 20分 基本概念 判断题选择题填空
    • 插入排序复杂度
  • 50-60分 简答算法分析
    • 递归时间分析平摊时间分析基本分析
    • 求最大流
    • 二项堆根表情况
  • 20-30分 算法设计题 1-2个算法题
    • 分治
    • 动态规划
    • 贪心方法

考试重点

渐进记号
分治方法基本步骤适用条件场合
递归式代换法递归树方法主方法
快速排序算法归并排序算法的时间复杂度
递归函数时间分析以及相应要求最坏最好平均不考
循环不变式不考
快速排序要清楚工作原理时间复杂度

红黑树性质与二叉查找树有何不同
插入和删除的过程和时间复杂度不会考具体插入操作和删除操作
红黑树有10个节点画出包含最多最少红节点的红黑树等等
数据结构扩张方法的基本步骤
动态序区间树要了解是什么算法时间复杂度解决问题

动态规划贪心算法
动态规划的基本步骤要素
贪心算法的要素适用条件
算法例子要清楚
最长公共子序列
活动选择问题
贪心法的理论基础不作要求只要掌握概念
什么是最大独立子集最优子集独立子集

平摊分析是本课程的主要内容要掌握
平摊分析合计法了解记账法了解势函数方法掌握
定义势函数
验证势函数的正确性
进行平摊分析

二项堆斐波那契堆结构条件根表操作时间
概念要清楚
三个堆的各个操作的时间复杂度掌握
各个堆的结构要满足的条件
根表的形式
给一个根表在根表上完成一次抽取最小值操作画出完成操作前后的根表

流网络
ford-fulkerson方法掌握
用ford-fulkerson方法求最大流
push-relable方法不做要求

递归/分治策略/求解递归式

渐进记号


求解递归式

代入法


(取底求上界)

假设形式必须与求解形式保持严格一致!

x


v (取顶求上界/取底求下界)

  • 习题课例题

    取顶求上界

    取底求下界

递归树法


  • 习题课例题

主方法


  • 习题课例题


证明: 数学归纳法

归并排序






  • 习题课例题

快速排序





二叉树/红黑树/区间树




删除节点


红黑树



数据结构扩张


  • 找第i个最小值OS-select(x,i) O(lgn)
  • 求x序值OS-rank(T,x) O(lgn)
  • 插入和删除size域 O(lgn)
  • 插入或删除操作的时间为O(lgn)

  • 习题课例题

区间树





动态规划/贪心算法

动态规划

  • 带备忘的自顶向下
  • 自底向上

动态规划的要素:

  • 最优子结构

  • 重合子问题

装配线问题

  • 描述问题的最优解结构特征

cut and paste

  • 递归定义最优路线的最快时间


  • 自底向上计算最快时间
    FASTEST-WAY(a, t, e, x, n)

  • 构造最优解结构(输出最优路线)

矩阵链乘法


cut and paste

  • 递归定义最优解值

  • 自底向上计算最优解值


递归求解


具体解法:
(2条消息) 动态规划之——矩阵连乘全网最详细博文看这一篇就够了_刘扬俊的博客-CSDN博客_矩阵连乘

公共最长子序列LCS

  • 找出LCS问题最优子结构性质

  • 递归定义LCS值

  • 自底向上计算LCS值

    <A, B, C, B, D, A, B> <B, D, C, A, B, A>

贪心算法

  • 贪心选择性质
    贪心选择性质是应用贪心法求解的一个必要条件所谓选择性质是指所求问题的最优解可以通过一系列局部最优的贪心选择而得到局部最优=>全局最优贪心选择性质是区别与动态规划方法的一个重要特征因为贪心法在作出选择时并不依赖于将来的情况只需根据当前的情况即可作出选择

  • 最优子结构性质

活动选择问题

  • 动态规划方法

  • 贪心方法

贪心选择性质:



背包问题

Huffman编码


胚理论

平摊分析(势函数法)



栈操作

二进制计数器

动态表







  • 插入和删除



二项堆/FIB堆

二项树




二项堆


  • 创建二项堆

  • 合并二项堆






  • case1

  • case2

  • case3/case4


  • 二项堆插入节点

  • 二项堆抽取(删除)最小节点

  • 二项堆减小关键字

  • 二项堆删除关键字

FIB堆





最大流/最小切









  • 例题