第2章算法分析ppt课件.ppt

《第2章算法分析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章算法分析基础学习要点:理解算法分析的任务和目的掌握渐近标记法在算法分析中的应用掌握算法分析的方法能够分析算法的最好、最坏、平均时间复杂度算法分析的任务：对设计出的每一个具体的算法，利用数学工具，讨论其复杂度。对算法的评价有两个大的方面：一是人对算法的维护的方便性。二是算法在实现运行时占有的机器资源的多少，即算法运行的时间和空间效率。目的：设计和选择出复杂性尽可能低的算法来解决问题。★2.1.1时间复杂性算法运行所需要时间资源的量，T=T(n,I,A)。其中，n表示算法要解的问题的规模；I表示算法的输入；A

2、表示算法本身。算法在一台抽象计算机上运行的时间。T(n,I)=其中，ti是计算机所提供的元运算执行一次所需时间；ei是算法用到元运算Oi的次数。2.1算法的复杂性三种情况下的时间复杂性最坏情况Tmax(n)=max{T(I)

3、size(I)=n}最好情况Tmin(n)=min{T(I)

4、size(I)=n}平均情况Tavg(n)=其中，I是问题的规模为n的实例，p(I)是实例I出现的概率。2.1.2空间复杂性算法运行所需要空间资源的量，S=S(n,I,A)。其中，n表示算法要解的问题的规模；I表示算法的输入；A

5、表示算法本身。算法在一台抽象计算机上运行时所占用的空间。分析起来比时间复杂性简单，本课程以时间复杂性为讨论主体。2.1.3渐近复杂性对于T(n)，如果存在f(n)，使得当n→∞时有(T(n)-f(n))/T(n)→0，那么，就说f(n)是T(n)当n→∞时的渐近性态。又称算法A的渐近复杂性。在数学上，f(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。例如，T(n)＝3n2+4nlogn+7，则f(n)的一个答案是3n2，因为，此时有(T(n)-f(n))/T(n)=→0（当n→∞

6、）渐近复杂性分析只关心f(n)的阶！2.2.1评价算法的准则算法正确性算法结构（健壮性）最佳性时间复杂性空间复杂性2.2算法分析的一般方法2.2.2评价算法时间复杂性的一般方法分析并确定：算法的哪些参数决定算法的“输入规模”？原因：问题实例的输入规模较大的，算法得到输出需要更多的时间开销。明确：被分析算法的“关键操作”是什么？关键操作：算法中重要的操作，或所关心的操作。“关键操作的数量”→“算法的时间复杂度”！例：内排：(“比较类”)待排序元素之间的“比较”次数；待排序元素的“移动”次数。查找：待查找值x与数据

7、元素之间的“比较”次数。矩阵乘法：矩阵元之间的乘法/加法运算次数。算法分析的目标：考察算法的“关键操作”数，随“问题规模”而变化的规律。提高计算速度对不同时间复杂性函数的影响对比T(n)微秒lognnnlognn2n3n52n3nn!n=103.310331001毫秒0.1秒1毫秒59毫秒3.6秒n=405.340213160064毫秒1.7分12.7天3855世纪103世纪n=605.9603543600216毫秒1.3分366世纪1.3×1013世纪1066世纪多项式函数指数函数时间复杂性函数用现在的计算机

8、用快100倍的计算机用快1000倍的计算机nN1100N11000N1n2N210N231.6N2n3N34.64N310N3n5N42.5N43.98N42nN5N5+6.64N5+9.973nN6N6+4.19N6+6.29算法时间复杂度的渐近表示算法的时间开销随问题规模增大的变化趋势。例2-1：简单选择排序算法的“比较”次数0123456…n-1a:(2,5,8,

9、12,9,20,15,…,66)

10、

11、↑↑小大ij(K)voidSELECT_SORT(Typea[],intn){FOR(inti=0;i<=

12、n-2;i++){intk=i;FOR(intj=i+1;j<=n-1;j++){IF(a[j]

13、集合ⅱg(n)不小于f(n)，且g(n)是“简洁”的函数。例如，当n≥10时，有2n2+11n-10≤3n2，所以有2n2+11n-10=O(n2)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(cf(n))=O(f(n))⑸g