算法剖析和计算复杂性理论.ppt

算法分析与计算复杂性理论;课程简介;课程内容;预计进度安排;教材与参考书;学习安排;引言: 理论上的可计算与现实上的可计算 ;投资问题;蛮力算法的代价; T(n) = 2 T(n?1) + 1，T(1) = 1，;其他问题;Algorithm + Data Structure = Programming;算法研究的重要性;理论上的可计算：可计算性理论;算法至少具有指数时间：理论上可计算——难解的 多项式时间的算法：现实上可计算——多项式时间可解的 对数多项式时间的算法：高度并行可解的;计算复杂性理论;例1 货郎担问题 问题：有穷个城市的集合C = { c1, c2, …, cm}, 正整数d (ci, cj) = d (cj, ci), 1? i j ? m. 解： 使得 k1, k2, …, km是1, 2 …, m 的置换且满足 ;;算法;算法的描述：伪码;伪码的例子：插入排序;算法的时间复杂度;;函数渐近的界;函数渐近的界的基本性质;证明(只证明第一种情况);定理1.2 设 f, g, h是定义域为自然数集合的函数， (1) 如果 f =O(g)且 g=O(h)，那么 f =O(h). (2) 如果 f =?(g)且 g=?(h)，那么 f =?(h). (3) 如果 f =?(g)和 g=?(h)，那么 f =?(h).;基本函数类;例题;例题;多项式时间的算法;多项式函数与指数函数; ;问题的复杂度分析;不同复杂性类的基本层次结构;;算法及计算复杂性理论的拓广