南开大学算法导论第二章课件.pdf

第二章算法分析基础 苏明 1 算法分析 什么叫一个算法好，运行的有效率？ 概念设计：效率 2 定义效率 提出效率定义(1) 当实现一个算法时，如 果它在真实的输入实例上运行的快，那 么这个算法是有效的。 寻找效率的定义：与平台无关，实例无 关，并且随着输入规模的增长是可以预 测的 3 定义效率 提出效率定义(2) 在分析的层次上，如 果一个算法与蛮力搜索(Brute Force)比 较，最坏情况下达到质量上更好的性能， 就说这个算法是有效的。 4 5 定义效率 一个算法被称为是多项式时间的如果满足 如下的性质： 当算法输入的规模增长时， 算法的运行时间是多项式有界的。也就 是：存在常数c0, d0, 使得对于每一个 问题输入的规模N, 算法的运行都能够在 cN d 步骤内完成。 6 定义效率 提出效率定义(3) 如果一个算法有多项式 运行时间，称为这个算法是有效的。 来自于数学形式和经验证据 但并不绝对反映真实的运行时间 符合实际情况的合理近似 7 定义效率 注记： 这种定义有利于一般性的研究 这种定义能够清楚的表达：对某个问题不存在有效 的算法 6.02 × 1023 × N20 也是多项式时间,但是在实际上是 不可行的。 实际中，大多数开发出的多项式时间的算法中幂次 指数，系数，常数项都比较小。 一些最坏情形是指数阶复杂度的算法也可能广泛使 用，这种情形极少出现。 能够改进指数阶穷举算法的要点在于发现问题内在 的一些特殊结构。 8 增长的渐进阶 为什么需要这样一个概念？ 得到一个准确的界是很困难的； 我们的目标是识别类似行为算法的大类， 按照粗粒度进行分析； 讨论算法执行的步数可能依赖于所使用 的语言，因此复杂度的多项式系数会不 一样。 9 复杂度符号 因为上述原因，希望以不受常数因子， 低项影响的方式表达运行时间的增长率。 O,Ω, Θ 10 复杂度符号 Upper bounds. T(n) is O(f(n)) if there exist constants c 0 and n0 ≥ 0 such that for all n ≥ n0 we have T(n) ≤ c · f(n). Lower bounds. T(n) is Ω(f(n)