算法复杂度.ppt

* * * * * * * * * * * * * * * * * 复杂性的渐近行为及其阶 关于记号O(g(N))的讨论 记号O的运算规则（某书给出） 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(…)未定义时，等号左边+和?的含义？ f(N), 若f(N) ? g(N) 其中max(f(N) , g(N)) = g(N), 若f(N) g(N) * 复杂性的渐近行为及其阶 关于记号O(g(N))的讨论 一种解释（另一本书给出）：O(g(N)) = { f(N) | ?C 0.?N0 0.?N ?N0. 0 ? f(N) ? Cg(N) } 符号O(g(N)) 在此给出了明确的数学意义 写f(N) ? O(g(N))容易理解( 而不是f(N) = O(g(N)) ) 但解释O(f(N)) + O(g(N)) 和O(f(N)) ? O(g(N))中的+和?（尤其是 ?）仍然有困难 导致各书仍继续使用f(N) = O(g(N))记号，使得读者难理解 * 复杂性的渐近行为及其阶 其他渐近意义下的记号 下界记号? 若f 和g是正整数集上的正函数，若存在大于0的常 数C和自然数N0，使得N ? N0时有f(N) ? Cg(N), 则 称：在N充分大时，Cg(N)是函数f(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)同阶 还有其他记号 * 复杂性的渐近行为及其阶 算法与渐近时间复杂性的关系 算法 渐近复杂 在C1上可 在C2上可解 N1和N2的关系 性T(N) 解规模N1 解规模N2 A1 N N11 N21 N21 = 10N11 A2 NlogN N12 N22 N22 ? 10N12 A3 N2 N13 N23 N23 = 10N13 A4 N3 N14 N24 N24 = 10N14 A5 2N N15 N25 N25 = N15+ log10 A6 N! N16 N26 N26=N16+小的常数 同一问题六个算法, 在C1和C2上运行, C2的速度是C1 10倍. 从Ti(N2i)=10Ti(N1i)(i =1, …, 6)解出关系式见上表 3 * 复杂性的渐近行为及其阶 复杂性渐近分析的重要性 对于低效算法，计算机速度数10甚至100倍的增长基本上不带来求解规模的增益 限制求解问题规模的主要根源是算法渐近复杂性的阶 ? 前四个算法的渐近时间复杂性与规模N的一个确定的幂同阶，机器速度的乘法增长带来求解规模的乘法增长。这类算法称为多项式算法 ? 后两个算法的渐近时间复杂性与规模N的一个指数函数同阶，只能带来求解规模的加法增长 这些结论在问题规模充分大时才成立 * 算法复杂性渐近阶的分析 如何分析具体算法的复杂性渐近阶 算法是用程序来表达的，算法复杂性渐近阶分析就是对其程序的相应分析 针对所用编程语言，给出一套可操作的分析规则 分析程序的语句、程序块和函数时，可用局部的规模参数作为复杂性函数的自变量。整个程序的复杂性函数还是以整个程序的输入规模为自变量 对串行算法，其时间复杂性等于相应程序每个语句的时间复杂性之和。若对每种语句所需时间都有度量规则，则算法所需时间就是一个求和问题 运用O、 ?和? 的运算规则就可进行所需分析 * 算法复杂性渐近阶的分析 基本运算和基本语句 赋值、比较运算、算术运算、逻辑运算和读写变量等需1个单位时间 下标变量和结构体的域的访问等需1个单位时间 if(C) S1 else S2只需TC + max(TS1, TS1)个单位时间 while(C) S所需单位时间数：(TC + TS) ? 循环次数 函数调用：控制转移的时间+执行被调函数的时间 递归函数：需要从所需时间的归纳定义（递归方程）中求解 基于这些规则可以计算整个程序的复杂性函数 * 小 结 本讲座小结 概要介绍计算复杂性理论、计算所需资源的多少是衡量计算复杂性的依据 概要介绍复杂性的渐近行为、渐近意义下的