算法设计与分析_第1章_概述2.pdf

《算法设计与分析_第1章_概述2.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、算法设计与分析第1章算法概述（2）学习要点算法在计算机科学中的地位算法的概念算法分析算法的计算复杂性概念算法渐近复杂性的数学表述2算法的渐近复杂性T(n),asn;若存在t(n),使得(T(n)-t(n))/T(n)0，asn;则称t(n)是T(n)的渐近性态，为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，它比T(n)简单,是T(n)略去低阶项留下的主项2T(n)=3n+4nlogn+722t(n)=3n说：算法运行时间是O(n)复杂性分析的简化用渐近复杂性t(n)代替T(n)3算法的渐近复杂性渐进复杂性分析的进一步简

2、化只关心“阶”,不关心常数因子假设算法中所有不同的基本运算各执行一次所需时间均为一个单位时间结论:渐近分析的思维：只考虑当问题的规模充分大时,算法复杂性在某些代表性输入的渐进意义下的阶4渐近分析的记号(1)5渐近分析的记号(2)f(n),g(n)是定义在正数集上的正函数在下面的讨论中，对所有n，f(n)0，g(n)0。（1）渐近上界记号OO(g(n))={f(n)存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}f(n)上有界,g(n)是上界函数f(n)的阶不高于g(n)的阶集合（2）渐近下界记号(g(n))={f(n)存在正常数

3、c和n0使得对所有nn0有：0cg(n)f(n)}f(n)下有界,g(n)是下界6渐近分析的记号(3)（3）紧渐近界记号(g(n))={f(n)存在正常数c1,c2和n0使得对所有nn有：cg(n)f(n)cg(n)}012f(n)=O(g(n))且f(n)=(g(n))定理1：(g(n))=O(g(n))(g(n))实际中，通常根据渐近上界和渐近下界来证明渐近紧界，而不是根据渐近紧界来得到渐近上界和渐近下界。7渐近分析的记号(4)（4）非紧上界记号oo(g(n))={f(n)对于任何正常数c>0，存在正整数n0>0使得对所有nn有：0

4、f(n)0，存在正整数n>0使得对所有nn有：0cg(n)

5、1=2n2+f(n)，其中f(n)是(n)中某个函数。等式和不等式中渐近记号O,o,和的意义是类似的。工程做法舍去低阶项,忽略后续的常量323Example:3n+90n–5n+6046=Θ(n)9渐近分析记号-BigOh例子222n+11n-10=O(n)22因为2n+11n-10≤3n（当n≥10）2100n+5=O(n)因为100n+5≤100n+n(当n≥5)=101n≤101n223n-100n+6≠O(n)2因为当n>c时cn<3n10渐近分析记号-BigOmega例子32证明：n=(n)11渐近分析记号-BigTheta例子2

6、证明(1/2)n(n-1)=(n)因为Oand上界：下界：12渐近分析中函数比较两个函数的渐近比较和两个实数的比较之间的类比关系:f(n)=O(g(n))ab;f(n)=(g(n))ab;f(n)=(g(n))a=b;f(n)=o(g(n))ab.13渐近分析记号的若干性质(1)（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)

7、)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))；14渐近分析记号的若干性质(2)（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))；15渐近分析记号的若