北京大学屈婉玲算法设计与分析必威体育精装版课件06.pdfVIP

第6章算法分析与 问题的计算复杂度 6.1 平凡下界 6.26.2 直接计数求解该问题所需要的最少运算直接计数求解该问题所需要的最少运算 6.3 决策树 6.4 检索算法的时间复杂度分析 66.55 排序算法的时间复杂度分析排序算法的时间复杂度分析 6.6 选择算法的时间复杂度分析 算法正确性 • 正确性正确性 在给定有效输入后在给定有效输入后,, 算法经过有限时间的算法经过有限时间的 计算并产生正确的答案, 就称算法是正确的. •• 正确性证明的内容正确性证明的内容：： – 方法的正确性证明——算法思路的正确性. 证明 一系列与算法的工作对象有关的引理系列与算法的工作对象有关的引理、定理以定理以 及公式.  – 程序的正确性证明程序的正确性证明——证明所给出的证明所给出的一系列指系列指 令确实做了所要求的工作. 2 工作量‐‐时间复杂性分析 计量工作量的标准: 对于给定问题,该算法所执行 的基本运算的次数的基本运算的次数. 基本运算的选择：根据问题选择适当的基本运算 问题 基本运算 在表中查找x 比较 实矩阵相乘 实数乘法 排序排序 比较较 遍历二叉树 置指针 两种时间复杂性: 最坏情况下的复杂性W(n) 平均情况下的复杂性平均情况下的复杂性AA ((n)) 3 占用空间‐‐空间复杂性分析 • 两种占用 – 存储程序和输入数据的空间存储程序和输入数据的空间 – 存储中间结果或操作单元所占用空间‐‐额外空间 •• 影响空间的主要因素影响空间的主要因素：： – 存储程序的空间一般是常数(和输入规模无关) – 输入数据空间为输入规模输入数据空间为输入规模 OO((n)) – 空间复杂性考虑的是额外空间的大小 • 额外空间相对于输入规模是常数额外空间相对于输入规模是常数, 称为称为原地工作的原地工作的 算法. • 两种空间复杂性:  – 最坏情况下的复杂性 – 平均情况下的复杂性. 4 简单性 • 含义：算法简单，程序结构简单.  • 好处：容易验证正确性 便于程序调试 • 简单的算法效率不一定高. 要在保证一定效率的前提下力 求得到简单的算法 5 基于时间的最优性 • 含义：指求解某问题算法类中效率最高的算法 • 两种最优性 最坏情况下最优：设A 是解某个问题的算法,, 如果在解这 个问题的算法类中没有其它算法在最坏情况下的时间复杂 性比A 在最坏情况下的时间复杂性低, 则称A 是解这个问 题在最坏情况下的最优算法题在最坏情况下的最优算法. 平均情况下最优：设A 是解某个问题的算法, 如果在解这 个问题的算法类中没有其它算法在平均情况下的时间复杂 性比A 在平均情况下的时间复杂性低, 则称A 是解这个问 题在平均情况下的最优算法题在平均情况下的最