2023-02-20

2022Fall_算法导论笔记

算法复习

往年试题:
CLRS1
CLRS2

考试题型:

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

考试重点

渐进记号
分治方法“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，基本步骤“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，适用条件“bd-box<h-char class=“bd bd-beg“>“>（场合“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）
递归式“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，代换法“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，递归树方法“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，主方法“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>。
快速排序算法“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，归并排序算法的时间复杂度
递归函数时间分析以及相应要求“bd-box<h-char class=“bd bd-beg“>“>（最坏“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>、最好“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>、~~平均不考~~“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）
循环不变式“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，（不考“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）
快速排序“bd-box<h-char class=“bd bd-beg“>“>（要清楚工作原理“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，时间复杂度“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）

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

动态规划“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，贪心算法“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，
动态规划的基本步骤“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，要素
贪心算法的要素“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，适用条件
算法例子要清楚“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>：
最长公共子序列
活动选择问题
贪心法的理论基础“bd-box<h-char class=“bd bd-beg“>“>（不作要求“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，只要掌握概念“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）
什么是最大独立子集“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>、最优子集“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>、独立子集

平摊分析“bd-box<h-char class=“bd bd-beg“>“>（是本课程的主要内容“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，要掌握“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）
平摊分析“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，合计法“bd-box<h-char class=“bd bd-beg“>“>（了解“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）<h-char class=“bd bd-beg“>，记账法“bd-box<h-char class=“bd bd-beg“>“>（了解“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，势函数方法“bd-box<h-char class=“bd bd-beg“>“>（掌握“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）
定义势函数“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，
验证势函数的正确性
进行平摊分析

二项堆“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>、斐波那契堆“bd-box<h-char class=“bd bd-beg“>“>（结构“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>、条件“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>、根表“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>、操作时间“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）
概念要清楚
三个堆的各个操作的时间复杂度“bd-box<h-char class=“bd bd-beg“>“>（掌握“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）
各个堆的结构“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，要满足的条件
根表的形式
给一个根表“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，在根表上完成一次抽取最小值操作“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，画出完成操作前后的根表

流网络
ford-fulkerson方法“bd-box<h-char class=“bd bd-beg“>“>（掌握“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）
用ford-fulkerson方法求最大流
push-relable方法“bd-box<h-char class=“bd bd-beg“>“>（不做要求“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>）

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

渐进记号

求解递归式

代入法

(取底求上界)

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

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条消息) 动态规划之——矩阵连乘“bd-box<h-char class=“bd bd-beg“>“>（全网最详细博文“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>，看这一篇就够了“bd-box<h-char class=“bd bd-beg“>“><h-char class=“bd bd-beg“>！<h-char class=“bd bd-beg“>）_刘扬俊的博客-CSDN博客_矩阵连乘

公共最长子序列LCS

找出LCS问题最优子结构性质
递归定义LCS值
自底向上计算LCS值

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

贪心算法

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