2023-02-20

2022Fall_算法导论笔记

算法复习

往年试题:
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>

贪心算法

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