算法分析与设计-第02章讲解.ppt

算法设计与分析 主讲 王海艳 计算机学院 wanghy@njupt.edu.cn 2.1 算法复杂度 2.1.1 什么是好的算法 一个好的算法应具有以下4个重要特性: 正确性(correctness)：算法的执行结果应当满足预先规定的功能和性能要求。 简明性(simplicity)：算法应思路清晰、层次分明、容易理解、利于编码和调试。 效率(efficiency)：算法应有效使用存储空间，并具有高的时间效率。 最优性（optimality）：算法的执行时间已达到求解该类问题所需时间的下界。 2.1.2 影响程序运行时间的因素 2.1.3 算法的时间复杂度 时间复杂度 一个算法的时间复杂度(time complexity)是指算法运行所需的时间。 设有一个在抽象机上运行的算法A，I是某次运行时的输入数据，其规模为n，则算法A的运行时间T是n和I的函数，记做T(n, I)。又设在该次运算中抽象机的第i个基本运算Oi的执行次数为?i，1≤i≤m，?i也是n和I的函数，记做?i(n, I)。那么，算法A在输入为I时的运行时间是： 2.1.4 使用程序步分析算法 通过程序步来分析算法的时间复杂度： 2.1.5 算法的空间复杂度 2.2 渐近表示法 程序步的精确计算是困难的，且程序步并不能确切反映程序运行的实际时间。 因此引入渐近时间复杂度,使用程序步在数量级上估计一个算法的执行时间，从而实现算法的事前分析。 在数学上，算法的渐近复杂度t(n)是T(n) 的渐近表达式，是T(n)略去低阶项留下的主项，它比T(n) 简单。 当n→∞时，有(T(n)-t(n))/T(n) →0。 例如: 3n2+4nlogn+7 与 3n2 渐近分析的记号：O、Ω、 ? 、o、ω 在下面的讨论中， 假设对所有n，f(n) ≥0，g(n) ≥0。 2.2.1 大O记号(渐近上界记号) 2.2.2 ?记号（渐近下界记号） 2.2.3 ?记号（紧渐近界记号） 2.2.3 ?记号（紧渐近界记号） 2.2.4 小o记号（非紧上界记号） 2.2.4 小o记号（非紧上界记号） 2.2.4+ ?记号（非紧下界记号） 定义2-5 如果对于任何正常数c0都存在正整数n0 0，使得当n? n0时有f(n)＞cg(n) （等价于n??时，f(n)/g(n)??），则称函数f(n)当n充分大时的阶比g(n)高，记做f(n)＝?(g(n))。 渐近分析中函数比较 f(n)= O(g(n)) ? f(n) ? g(n); f(n)= ?(g(n)) ? f(n) ? g(n); f(n)= ?(g(n)) ? f(n) = g(n); f(n)= o(g(n)) ? f(n) g(n); f(n)= ?(g(n)) ? f(n) g(n). 附录：渐近分析记号的若干性质 （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)) ；其中c是一个正的常数； 如果g(n)= O(f(n)) ? 则O(f(n))+O(g(n)) = O(f(n)) 。 f=O(f)。 2.2.5 算法按时间复杂度分类 2.3 递推关系 2.3.1 递推方程 2.3.2 替换方法 2.3.3 迭代方法 2.3.4 主方法 例2-5 f(n) =2n+3=?(n) 对所有n，2n+3≥2n， 可选c=2，n0=0。对于n≥n0， f(n)=2n+3≥2n， 所以，f(n)= ?(n)， 即2n +3??(n)。