算法设计与分析第二讲

《算法设计与分析第二讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、智能信息处理研究中心（RCIIP）计算机算法设计与分析潘海为1智能信息处理研究中心（RCIIP）算法的复杂性算法复杂性=算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。2智能信息处理研究中心（RCIIP）算法的时间复杂性（1）最坏情况下的时间复杂性T(n)=max{T(I)

2、size(I)=n}max（2）最好情况下的时间复杂性T(n)=min{T(I)

3、size(I)=n}min（3）平均情况下的时间复杂性T(n)=p(I)T(I)avgsize(I)n其中I是问题的规模

4、为n的实例，p(I)是实例I出现的概率。3智能信息处理研究中心（RCIIP）算法的渐近复杂性T(n),asn;(T(n)-t(n))/T(n)0，asn;t(n)是T(n)的渐近性态，为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。4智能信息处理研究中心（RCIIP）渐近分析的记号在下面的讨论中，对所有n，f(n)0，g(n)0。（1）渐近上界记号OO(g(n))={f(n)

5、存在正常数c和n使得对所有nn有：000f(n)cg(n)}（2）渐近下

6、界记号(g(n))={f(n)

7、存在正常数c和n使得对所有nn有：000cg(n)f(n)}5智能信息处理研究中心（RCIIP）渐近分析的记号（3）非紧上界记号oo(g(n))={f(n)

8、对于任何正常数c>0，存在正数和n>0使得对所有nn有：0f(n)

9、对于任何正常数c>0，存在正数和n>0使得对所有nn有：0cg(n)

10、o(f(n))智能信息处理研究中心（RCIIP）渐近分析的记号（5）紧渐近界记号(g(n))={f(n)

11、存在正常数c,c和n使得对所有120nn有：cg(n)f(n)cg(n)}012定理1：(g(n))=O(g(n))(g(n))7智能信息处理研究中心（RCIIP）渐近分析记号在等式和不等式中的意义f(n)=(g(n))的确切意义是：f(n)(g(n))。一般情况下，等式和不等式中的渐近记号(g(n))表示(g(n))中的某个函数。例如：2n2+3n+1=2n2+(n)表示2n2+3n+1=2n2+f(n

12、)，其中f(n)是(n)中某个函数。等式和不等式中渐近记号O,o,和的意义是类似的。8智能信息处理研究中心（RCIIP）渐近分析中函数比较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.9智能信息处理研究中心（RCIIP）渐近分析记号的若干性质（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(

13、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))；10智能信息处理研究中心（RCIIP）渐近分析记号的若干性质（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

14、(g(n))g(n)=(f(n))；11智能信息处理研究中心（RCIIP）渐近分析记号的若干性质（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))。12智能信息处理研究中心（RCIIP）渐近分析记号的若干性质规则O(f(n))+O(g(n))=O(max{f(n),g(n)})

15、证明：对于任意f(n)O(f(n))，存在正常数c和自然数n，使得对所有nn，有1111f(n)cf(n)。11类似地，对于任