USTC算法基础 2022-Fall-Final.pdf
需积分: 0 150 浏览量
2023-02-18
21:09:13
上传
评论
收藏 207KB PDF 举报
算
法
基
础
2022-Fall-Final
1
期
中
前
的
知
识
算法的思想和方法的理解，高等数据结构之前少一点
O Ω渐进复杂度概念,怎么去算函数渐进表达
主函数(期末必考)
排序 涉及思想 快排 堆排 复杂度 是不是原址排序 是不是稳定的 基于比较算法
最多
线性排序 桶排序 基数排序 计数排序 中位数 求第几大
高等数据结构：用斐波那契堆结构求最小生成树，DecreaseKey摊还时间复杂
度，红黑树的设计思想：为了达到二叉搜索树的平衡
这部分占20~30分
2
期
中
后
期末考察重点：设计思想
动态规划
贪心
分治
1. 动态规划 设计一个算法求解问题，分成子问题，状态转移方程写出来，
边界条件写清楚 ，分析算法，时间复杂度， 把大问题分成小问题，自底
向上，最优子结构（正确性前提），重叠子问题（有效性前提）如果大
量重复子问题没有起不到加速的效果
2. 贪心算法，根据当前局部最优解一步步前进，最优子结构，当前的一步
都是最优解的一部分，有的情况下可以取得最优解，拟阵结构不考
3. 分治思想，把问题分成子问题，和动态规划有区别，分出来的子问题可
能是各异的，不一定自底向上，只是把问题分解合并得到原问题的解，
主方法解递归式，两个问题合并需要一定复杂度
摊还时间复杂度：和最优最差的区别，实际还是最差时间复杂度，一系列操作
最差复杂度的平均，比如找n个数，第最小的第i个数，找很多次可以先排序再
每次常数时间找到第i小的，摊还分析超纲但也可能会考
图算法之类的 string match
算法分析思想额外思想，
图算法：
资源评论
