算法设计与分析15复习及答疑v2详解.pptx

算法设计与分析1考试及答疑安排n考试时间：7月2日（周四）15:30-17:30 n答疑安排n地点：教三楼918n7月2日：08:00点12:00点n注意考场纪律 禁止：禁止：1.1.夹带纸制品；夹带纸制品；2.2.使用手机、使用手机、PDAPDA等等2复习要求n计算题计算题 5道大题算法设计与分析3第1章n算法复杂性的概念n时间、空间复杂性n5种渐进复杂性定义 O,o,的概念的概念n!证明证明 f(n)=?(g(n)？:5种渐近复杂性n注意：O、与o、在定义上的区别：n存在正常数c和n0，使得对所有n n0有n对于任何正常数c0，存在正数n0 0nf(n)=O(g(n)a b;渐近上界渐近上界nf(n)=(g(n)a b;渐近下界渐近下界 nf(n)=(g(n)a=b;紧渐近界紧渐近界nf(n)=o(g(n)a b.非紧下界非紧下界 算法设计与分析4第1章n 算法时间复杂性分析方法n!给定算法步骤，分析各步执行时间，分析算法时间复杂给定算法步骤，分析各步执行时间，分析算法时间复杂性性算法设计与分析5第2章n 递归法的基本原理/步骤n分治法基本原理/步骤、适用条件n递归函数(了解)n用特征方程解递归方程的通解 1）!线性齐次递归方程线性齐次递归方程 2）线性非齐次递归方程（不做要求）算法设计与分析6第 2 章 原理、步骤/代码/伪代码、时间复杂性,计算例子n快速排序n合并排序n线性时间选择n平面最近点对 算法设计与分析7第 3章 动态规划n 基本原理、要素（了解）最优子结构性质n应用范例 原理、递推方程、步骤/代码/伪代码、时间复杂性,计算例子n最长公共子序列n最大子段和n凸多边形最优三角剖分n背包问题算法设计与分析8第 4章 贪心算法n 贪心算法基础（了解）1）基本要素 最优子结构性质、贪心选择性质 2）贪心算法与动态规划算法的差异n应用范例:原理、步骤/代码/伪代码、时间复杂性,计算例子n（1）活动安排问题n（2）哈夫曼编码n（3）单源最短路径n（4）最小生成树算法设计与分析9第 5 章 回溯法n原理（了解）形式化表示，完全/部分/可行/最优/不可行解，搜索空间；深度优先搜索策略；子集树、排列树问题；n算法框架（了解）递归回溯框架 迭代回溯框架；算法设计与分析10第 5 章 回溯法原理、步骤/代码/伪代码、时间复杂性,计算例子n装载问题（背包问题）nn皇后问题n图的m着色问题n旅行商问题算法设计与分析11第 6 章 分支限界法n原理与算法框架（了解）解空间；界限函数，剪枝与搜索过程；n 应用范例原理、上下界限函数设计、步骤/代码/伪代码、时间复杂性、解空间树,计算例子！（1）0-1背包问题12问题完全解界限40,100w=0,v=0ub=100,S=?,?,?,?w=4,v=40ub=40+(10-4)*6,S=1,?,?,?w=0,v=0ub=0+10*6,S=0,?,?,?11123w=4+7=11,S=1,1,?,?w=4,v=40ub=40+0+(10-4)*5,S=1,0,?,?45无效死结点(wC)w=4+5=9,v=65 ub=65+(10-4-5)*4,S=1,0,1,?w=4,v=40ub=40+(10-4)*4,S=1,0,0,?67无效死结点(wC)w=9,v=65 ub=65,S=1,0,1,09w=12,S=1,0,1,18剪枝条件:ub 40物品2单位价值物品3单位价值物品4单位价值物品4单位价值