计算复杂性和算法分析计算机科学导论.PPT

* * * * * * * * * * * * * * * * * * * * * * * 复杂性的渐近行为及其阶 例：估计下面二重循环的最坏时间复杂性的阶 for(i = 1; i N; i++) for(j = 1; j i; j++) s1; s2; s3; s4; 其中sk(k =1, 2, 3, 4)都是赋值语句 外循环执行N次，需时间 (5a +t) ? N(N+1)/2 + (a +t) ? N 因此上界为O(N2) 这是规模充分大时的上界 这个上界的阶越低，则评估就越精确，结果就越有价值 * 复杂性的渐近行为及其阶 关于记号O(g(N))的讨论 当讨论复杂算法上界时，很希望上界记号O(g(N)) 能参与到复杂性计算中 例如，上例内循环的上界O(i)，则累加起来便是外循环的时间复杂性 T(N) = ?O(i) = O(?i) = O(N(N+1)/2) = O(N2) 若希望如此，则需要有一些演算规则，并证明其正确性 i=1 n i=1 n * 复杂性的渐近行为及其阶 关于记号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 ? 方程Ti(N2i)=10Ti(N1i)是求解N2i和N1i之间的关系 ? 等式Ti(N2i)=10Ti(N1i)的含义是：第i个算法在C1上运行10倍于C2上运行的时间，则等号两边效果一样 同一问题六个算法, 在C1和C2上运行, C2的速度是C1 10倍. 从Ti(N2i)=10Ti(N1i)(i =1, …, 6)解出关系式 * 复杂性的渐近行为及其阶 算法与渐近时间复杂性的关系 算法 渐近复杂 在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 * 复杂性的渐近行为及其阶 复杂性渐近分析的重要