北邮-算法设计期末复习.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：0.76M 资料格式：pdf 举报版权申诉

de1cc0ad-bf12-4bd5-bd45-75ff1c5f9009.pdf-第1页.png

第1页 / 共11页

de1cc0ad-bf12-4bd5-bd45-75ff1c5f9009.pdf-第2页.png

第2页 / 共11页

de1cc0ad-bf12-4bd5-bd45-75ff1c5f9009.pdf-第3页.png

第3页 / 共11页

de1cc0ad-bf12-4bd5-bd45-75ff1c5f9009.pdf-第4页.png

第4页 / 共11页

de1cc0ad-bf12-4bd5-bd45-75ff1c5f9009.pdf-第5页.png

第5页 / 共11页

de1cc0ad-bf12-4bd5-bd45-75ff1c5f9009.pdf-第6页.png

第6页 / 共11页

de1cc0ad-bf12-4bd5-bd45-75ff1c5f9009.pdf-第7页.png

第7页 / 共11页

de1cc0ad-bf12-4bd5-bd45-75ff1c5f9009.pdf-第8页.png

第8页 / 共11页

文本预览

算法设计与分析复习及答疑安排关于算法的那些事王晓茹

Scope 算法复杂性分析和渐进性原理分治法动态规划贪心算法回溯法 Description 一共五道大题，上述算法策略各选一个题目。

[ 答疑时间： ① QQ在线可随时答疑； ② 考前6月30日上午教3-918现场答疑； ]

第1章的复习（1） 1. 算法复杂性的概念 • 时间、空间复杂性 • 5种渐进复杂性定义 O, o, , ,  的概念 • ! 证明 f(n)=?(g(n)) ？: 5种渐近复杂性 • 注意：O、 与o、 在定义上的区别： • 存在正常数c和n0 ，使得对所有n n0有 • 对于任何正常数c>0，存在正数n0 >0 2. 用特征方程解递归方程的通解 n f(n)= O(g(n))  a  b; 渐近上界 n f(n)= (g(n))  a  b; 渐近下界 n f(n)= (g(n))  a = b; 紧渐近界 n f(n)= o(g(n))  a < b; 非紧上界 n f(n)= (g(n))  a > b. 非紧下界

题型：参见第一次作业

第2章分治法 1. 理解递归的概念和原理 2. 掌握设计有效的分治算法的方法 3. 利用范例学习： ① 二分搜索 ② 快速排序 ③ 合并排序 ④ 线性时间选择 4. 要求：能够流利写出范例中的算法伪代码，并能分析算法的时间复杂度。

第3章动态规划 1. 理解动态规划算法的概念。 2. 掌握动态规划算法的基本要素。（1）最优子结构性质（2）重叠子问题性质 3. 掌握设计动态规划算法的步骤。（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。

4. 范例学习：（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和 5. 要求： ① 范例中的算法能够流利写出伪代码； ② 算法同时要求实现求最优解和构造最优解； ③ 并能分析算法的时间复杂度。

分享到：

赞收藏

资料库

北邮-算法设计期末复习.pdf

相关推荐

课程资源

热门标签

最新资料