《算法设计与分析》(全).ppt

巢湖学院计算机科学与技术系 巢湖学院 巢湖学院计算机系 中国计算机学会 21世纪大学本科计算机专业系列教材 《算法设计与分析》 王晓东 编著 主要内容介绍 第1章、算法引论 第2章、递归与分治策略 第3章、动态规划 第4章、贪心算法 第5章、回溯法 第6章、分支限界法 第7章、概率算法 第8章、NP完全性理论 第9章、近似算法 第10章、算法优化策略 第1章 算法引论 1.1 算法与程序 1.2 表达算法的抽象机制 1.3 描述算法 1.4 算法复杂性分析 1.1、算法与程序 1.1、算法与程序 问题求解(Problem Solving) 1.2、表达算法的抽象机制 1.从机器语言到高级语言的抽象 1.2、表达算法的抽象机制 2.抽象数据类型 1.3、算法复杂性分析 1.3、算法复杂性分析 1.3、算法复杂性分析 1.3、算法复杂性分析 1.3、算法复杂性分析 渐近分析记号在等式和不等式中的意义 f(n)= ?(g(n))的确切意义是：f(n) ? ?(g(n))。 一般情况下，等式和不等式中的渐近记号?(g(n))表示?(g(n))中的某个函数。 例如：2n2 + 3n + 1 = 2n2 + ?(n) 表示 2n2 +3n +1=2n2 + f(n)，其中f(n) 是?(n)中某个函数。 等式和不等式中渐近记号O,o, ?和?的意义是类似的。 渐近分析中函数比较 f(n)= O(g(n)) ? a ? b; f(n)= ?(g(n)) ? a ? b; f(n)= ?(g(n)) ? a = b; f(n)= o(g(n)) ? a b; f(n)= ?(g(n)) ? a b; 渐近分析记号的若干性质 （1）传递性： f(n)= ?(g(n))， g(n)= ?(h(n)) ? f(n)= ?(h(n))； f(n)= O(g(n))， g(n)= O (h(n)) ? f(n)= O (h(n))； f(n)= ?(g(n))， g(n)= ? (h(n)) ? f(n)= ?(h(n))； f(n)= o(g(n))， g(n)= o(h(n)) ? f(n)= o(h(n))； f(n)= ?(g(n))， g(n)= ? (h(n)) ? f(n)= ? (h(n))； （2）反身性： f(n)= ?(f(n))；f(n)= O(f(n))；f(n)= ?(f(n)). （3）对称性： f(n)= ?(g(n)) ? g(n)= ? (f(n)) . （4）互对称性： f(n)= O(g(n)) ? g(n)= ? (f(n)) ； f(n)= o(g(n)) ? g(n)= ? (f(n)) ； 渐近分析记号的若干性质 （5）算术运算： O(f(n))+O(g(n)) = O(max{f(n),g(n)}) ； O(f(n))+O(g(n)) = O(f(n)+g(n)) ； O(f(n))*O(g(n)) = O(f(n)*g(n)) ； O(cf(n)) = O(f(n)) ； g(n)= O(f(n)) ? O(f(n))+O(g(n)) = O(f(n)) 。 渐近分析记号的若干性质 规则O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 的证明： 对于任意f1(n) ? O(f(n)) ，存在正常数c1和自然数n1，使得对所有n? n1，有f1(n) ? c1f(n) 。 类似地，对于任意g1(n) ? O(g(n)) ，存在正常数c2和自然数n2，使得对所有n? n2，有g1(n) ? c2g(n) 。 令c3=max{c1, c2}, n3 =max{n1, n2},h(n)= max{f(n),g(n)} 。 则对所有的 n ? n3，有 f1(n) +g1(n) ? c1f(n) + c2g(n) ? c3f(n) + c3g(n)= c3(f(n) + g(n)) ? c32 max{f(n),g(n)} = 2c3h(n) = O(max{f(n),g(n)}) . 算法渐近复杂性分析中常用函数 （1）单调函数 单调递增：m ? n ? f(m) ? f(n) ; 单调递减：m ? n ? f(m) ? f(n); 严格单调递增：m n ? f(m) f(n); 严格单调递减：m n ? f(m) f(n). （2）取整函数 ? x ? ：不大于x的最大整数； ? x ? ：不小于x的最小整数； 取整函数的若干性质 x-1 ? x ? ? x ? ? x ? x+1； ? n/2 ? + ? n/2 ? = n; 对于n ? 0，a,b是大于0的整数，有： ? ? n/a ? /