算法设计技巧与分析-第1章--算法基本概念之算法复杂度概要.ppt

《算法设计技巧与分析-第1章--算法基本概念之算法复杂度概要.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计技巧与分析AlgorithmsDesignTechniquesandAnalysis南方医科大学医工学院信息技术系第1章算法分析基本概念Content算法与程序简单的算法实例计算复杂性时间复杂性空间复杂性分析计算方法算法的复杂性分为设计算法追求的目标选用算法的准则时间复杂性需要的时间资源的量空间复杂性需要的空间资源的量设计出复杂性尽可能低的算法选择已有算法中复杂性最低者不是所有能计算的都有价值，不是所有有价值的都能被计算。——阿尔伯特.爱因斯坦AlgorithmComplexityTimeComplexit

2、y1估计算法运行的时间范围。2估算随着输入的增长，运算时间的增长率。1）有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限，程序将被强制结束。2）正在开发的程序可能需要提供一个满意的实时响应。AsymptoticRunTime令算法的输入为n，若算法的运行时间f(n)为n的m阶函数，则称f(n)是m阶的。一旦去除了表示算法运行时间的函数中的低阶项和首项常数，就称我们是在度量算法的渐进运行时间。分析算法的复杂性的目的:比较求解同一问题的两个不同算法的效率，而当要比较的两个算法的渐进复杂性的阶不相同时，只要能确

3、定出各自的阶就可以判定哪一个算法的效率高。Figure1.5MarkO：运行时间的上界Ω：在运行时间的一个常数因子内提供一个下界Θ：算法的精确阶о：说明两个函数属于不同的复杂性类SymbolO定义1.2令f(n)和g(n)是从自然数集到非负实数集的两个函数，如果存在一个自然数n0和一个常数c>0，使得：对于所有的n≥n0，有f(n)≤cg(n)，则称f(n)为O(g(n))，记作：f(n)=O(g(n))。UltimateForm如果存在，那么蕴含着SymbolΩ定义1.3令f(n)和g(n)是从自然数集到非负实数

4、集的两个函数，如果存在一个自然数n0和一个常数c>0，使得：对于所有的n≥n0，有f(n)≥cg(n)，则称f(n)为Ω(g(n))，记作：f(n)=Ω(g(n))。UltimateForm如果存在，那么蕴含着推论：f(n)是Ω(g(n))，当且仅当g(n)是O(f(n))。SymbolΘ定义1.4令f(n)和g(n)是从自然数集到非负实数集的两个函数，如果存在一个自然数n0和两个正常数c1和c2，使得：对于所有的n≥n0，有c1g(n)≤f(n)≤c2g(n)，则称f(n)为Θ(g(n))，记作：f(n)=Θ(g

5、(n))。UltimateForm如果存在，那么蕴含着推论：f(n)是Θ(g(n))，当且仅当f(n)=O(g(n))并且f(n)=Ω(g(n))。FigureExample1.5设：由于对,因此有；由于对,因此有。此外,由于对,因此有。极限方式：由于，因此有和。Example1.12考虑级数，显然n1logjjO(nlogn)=å=即又=那么同理得到算法1.7BRUTE-FORCEPRIMALITYTEST输入:正整数n≥2。输出:如果n是素数则输出为真，否则为假。1、s←2、forj←2tos3、ifj划分nt

6、henreturnfalse4、endfor5、returntrueAnalysis假定：可以在O(1)时间内计算出来；对任意的素数n：循环执行次数为-1，则算法是O()；考察对象1：算法中循环的执行次数；对任意的n值(如n为偶数)：循环执行次数为1，则算法是Ω(1)；推论：蛮力算法既不是Θ()也不是Θ(1)。ComplexityTypes令R为复杂性函数集合上由下列条件定义的关系：fRg当且仅当f(n)=Θ(g(n))。由这个关系导出的等价类称为复杂性类。例如：所有的二次多项式属于同一个复杂性类n2。问题：如何区

7、分属于不同复杂性类的两个函数？定义1.5令f(n)和g(n)是从自然数集到非负实数集的两个函数，如果对每一个常数c>0，存在一个正整数n0，使得：对于所有的n≥n0，都有f(n)

8、行时，需指明分配给该程序的内存大小。2.想提前知道是否有足够可用的内存来运行该程序。3.一个问题可能有若干个内存需求各不相同的解决方案，从中择取。1估算一个程序所能解决的问题的最大规模。SpaceUsed算法使用的空间：为了求解问题的实例而执行的计算步骤所需要的内存空间数目，不包括分配用来存储输入的空间。写入每一个内存空间都至少需要一定的时间。推论：令T(n