算法效率分析与分治法的应用ppt课件.ppt

《算法效率分析与分治法的应用ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法效率与分治算法的应用长沙市一中曹利国算法效率的评价算法的评估有时求解同一个问题常常有多种可用的算法，在一定的条件下当然要选择使用好的算法。用什么方法评估算法的好坏呢？通常使用算法复杂性这一概念来评估算法。算法评价算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法：事后统计的方法事前分析估算的方法算法评价一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：①依据的算法选用何种策略；②问题的规模.例如求100以内还是1000以

2、内的素数；③书写程序的语言.对于同一个算法,实现语言的级别越高,执行效率就越低；④编译程序所产生的机器代码的质量；⑤机器执行指令的速度。算法评价一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通过的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作，以该基本操作重复执行的次数作为算法的时间度量。算法评价一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间

3、量度记作T（n）=O（f（n））它表示问题规模n的增大算法执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。算法评价例如：在下列三个程序段中，①x:=x+1②fori:=1tondox:=x+1;③forj:=1tondofork:=1tondox:=x+1含基本操作“x增1”的语句x:=x+1的频度分别为1，n和n2，则这三个程序段的时间复杂度分别为O（1），O（n），O（n2），分别称为常量阶、线性阶和平方阶。算法评价算法还可能呈现的时间复杂度有：对数阶O（logn），指

4、数阶O（2n）等。在n很大时,不同数量级时间复杂度显然有O（1）

5、n2，它是语句频度表达式(n-1)(n-2)/2中增长最快的一项。算法评价类似于算法的时间复杂度，以空间复杂度作为算法所需存储空间的量度，记作S(n)=O(f(n))其中n为问题的规模(或大小)。一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。算法评价评价一个数学模型有以下几个原则：1.时间复杂度一个好的算法一般效率比较高。在竞赛中，试题常常会做一些算法运行时间上的限制。这就要求我们所建立的数学模型对应算

6、法的效率一定要符合要求。这也是最重要的一个原则。算法评价2.空间复杂度出于计算机自身的限制，程序在运行时一般只被提供有限的内存空间。这也就要求我们建立模型时顾及到这一点。但对于模型对应的算法来说，并不是要求空间越低越好，只要不超过内存限制就可以了。算法评价3.编程复杂度相对而言，“编程复杂度”的要求要略低一些。但是在竞赛中，如果建立的算法实现起来十分繁琐，自然不利于比赛。所以，在建立模型时（特别是在竞赛中）这点也要纳入考虑之中。影响算法效率的因素问题的算法模型的建立问题的数据结构选择算法评价一道题目可能对应

7、几种不同思想的模型，就要根据评价模型的标准来衡量一下，确定一个模型作为分析方向。这时的评价标准除了上述的时间、空间、编程三个标准外，还要加上一个思维的复杂度。算法评价所谓思维的复杂度，是指思考所耗费的时间和精力。如果我们确定了一个模型作为分析的方向（没有考虑思维复杂度），从问题原型到该数学模型的建模过程却十分复杂，导致思维耗费时间长，精力多，那自然是不合算的。总的来说，对于多种数学模型的选择，我们遵循“边分析，边选择”的原则。不同数据结构对算法效率的影响乘船问题：有N个人需要乘船，而每船最多只能载两人，且必

8、须同名或同姓。求最少需要多少条船。问题分析看到这道题，很多人都会想到图的数据结构：将N个人看作无向图的N个点，凡同名或同姓的人之间都连上边。要满足用船最少的条件，就是需要尽量多的两人共乘一条船，表现在图中就是要用最少的边完成对所有顶点的覆盖。这就正好对应了图论的典型问题：求最小边的覆盖。所用的算法为“求任意图最大匹配”的算法。分析使用“求任意图最大匹配”的算法比较复杂(要用到扩展交错树，对花的收缩等等)，效率也不