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>

贪心算法

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