
算法复习重点
算法复习重点
1.summary
2.第一章
3.第二章
二分搜索
合并排序 稳定 最坏Onlogn,平均Onlogn
简单版
改进版(非递归算法)
快速排序 最坏On^2 平均Onlogn
线性时间选择 On
循环赛
最接近点对问题 Onlogn
4.第三章
最优子结构性质
重叠子问题——他和分治的不同点(实际上很多和分治是一样的)
动态规划算法设计步骤
矩阵连乘——以最少的次数求出最终结果
第一种办法:自底向上
第二种方法:记录表方法——自顶向上
最长公共子序列——最长公共子序列,怎么找原问题和子问题!!倒着找!
扩展:三角剖分
最大子段和 On
0/1背包问题
5.第四章
理解贪心算法概念
掌握贪心算法基本要素
最优子结构性质
贪心选择性质
理解贪心和动态规划差异
理解贪心算法的一般理论
活动安排
背包问题
哈夫曼编码 很少考 太难了
最小生成树
Prime 最近顶点 On^2
Kruskal 最短边 Oeloge
单源最短路径 On^2
6.第五章
解向量、解空间树、剪枝函数、剪枝后的解空间树、伪代码、复杂度
理解回溯法的深度优先搜索策略
掌握回溯法解题的算法框架
轮船装载问题 O2^n
作业调度问题 On!
TSP旅行售货员问题 On!
N皇后问题
图的着色问题 Omn
1.summary