笔记参考：算法笔记、算法复习

复习视频： 【北大公开课】算法设计与分析、算法设计与分析期末速成

考题如下 自行划重点：

23 算法 回忆版 A卷：

5道选择：渐进界、回溯基于深搜、dp的条件（子问题最优、叠加）、贪心的条件（子结构、贪心）、dij不能处理负权

两道计算：

  • 解递推方程（不只算复杂度）：T(n)=4T(n/3)+n^2-7n+5
  • 对偶线性规划（不需要单纯形）：对偶性、松弛条件
    max x1 + x2
    s.t. x1 <= 5
    x2 <= 3
    x1 + 3x2 <= 11
    x1, x2 >= 0

两道算法理解：dp（该章第一个例子）、prim求最小生成树

三道算法设计：移掉 K 位数字、o(n²)求最长单调增子序列、最小费用流和运输问题（建模最大流运输问题）

23 算法 回忆版 B卷：

5道选择：函数渐进界、分支限界法基于广搜、dp条件、贪心条件、快排pivot选择复杂度区别

两道计算

  • 解递推方程：T(n)=3T(n/2)+n^2-7n+5
  • 求对偶线性方程 然后验证解在原始线性规划最优

两道算法理解：二分查找（给一个数组具体过程）、分支限界法求最短路 画出解空间树 包括最优解点 剪枝点 中间点

三道算法设计：循环日程赛、O(n²)求最长单调增子序列、匈牙利算法

image-20240326112517671