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

1、算法设计技巧与分析Algorithms Design Techniques and Analysis 南方医科大学医工学院 信息技术系 第1章 算法分析基本概念Content算法与程序简单的算法实例计算复杂性时间复杂性空间复杂性分析计算方法算法的复杂性分为 设计算法追求的目标选用算法的准则 时间复杂性 需要的时间资源的量空间复杂性 需要的空间资源的量设计出复杂性尽可能低的算法选择已有算法中复杂性最低者不是所有能计算的都有价值，不是所有有价值的都能被计算。 阿尔伯特. 爱因斯坦Algorithm ComplexityTime Complexity1 估计算法运行的时间范围。2 估算随着输入的增长

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

3、下界：算法的精确阶：说明两个函数属于不同的复杂性类Symbol O定义1.2 令f (n) 和g (n) 是从自然数集到非负实数集的两个函数，如果存在一个自然数n0和一个常数c 0，使得： 对于所有的nn0，有f (n) cg (n)， 则称f (n)为O (g (n ) ， 记作：f (n) = O (g (n )。Ultimate Form如果 存在，那么蕴含着Symbol 定义1.3 令f (n) 和g (n) 是从自然数集到非负实数集的两个函数，如果存在一个自然数n0和一个常数c 0，使得： 对于所有的nn0，有f (n) cg (n)， 则称f (n)为(g (n ) ， 记作：f

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

5、 。FigureExample1.5设：由于对 ,因此有 ； 由于对 ,因此有 。此外,由于对 ,因此有 。极限方式：由于 ，因此有 和 。Example1.12考虑级数 ，显然 n1log jjO(n log n)=即又=那么同理得到算法1.7 BRUTE-FORCE PRIMALITYTEST输入: 正整数 n 2 。输出: 如果 n 是素数则输出为真，否则为假 。1、s 2、for j 2 to s3、 if j 划分 n then return false4、end for5、return trueAnalysis假定： 可以在O (1)时间内计算出来；对任意的素数n：循环执行次数为

6、-1，则算法是O ( )；考察对象1：算法中循环的执行次数；对任意的n值(如n为偶数)：循环执行次数为 1，则算法是( 1)；推论： 蛮力算法既不是( )也不是(1) 。Complexity Types令R为复杂性函数集合上由下列条件定义的关系：f R g当且仅当f (n) = (g (n )。由这个关系导出的等价类称为复杂性类。例如：所有的二次多项式属于同一个复杂性类n2。问题： 如何区分属于不同复杂性类的两个函数？定义1.5 令f (n) 和g (n) 是从自然数集到非负实数集的两个函数，如果对每一个常数c 0，存在一个正整数n0，使得： 对于所有的nn0 ，都有f (n) cg (n)

7、， 则称f (n)是o (g (n ) 的 ，即f (n) = o (g (n ) 记作： f (n) g (n )。Symbol Ultimate Form如果 存在，那么蕴含着推论： f (n)=o(g (n )，当且仅当f (n)=O (g (n )并且g(n) O (f (n ) 。Complexity Types RelationSpace Complexity1. 多用户系统中运行时，需指明分配给该程序的内存大小。2.想提前知道是否有足够可用的内存来运行该程序。3.一个问题可能有若干个内存需求各不相同的解决方案，从中择取。1 估算一个程序所能解决的问题的最大规模。Space Used算法使用的空间：为了求解问题的实例而执行的计算步骤所需要的内存空间数目，不包括分配用来存储输入的空间。写入每一个内存空间都至少需要一定的时间。推论： 令T(n)和S(n)分别代表算法的时间复杂性和空间复杂性，则有S (n)=O (T(n ) 。Example1.17 1.18 1.19算法空间复杂度LINEARSEARCH(1)MERGE(n)BOTTOMUPSORT(n)考虑：算法SELECTIONSORT和INSERTIONSORT的空间复杂性？Tradeoff许多问题需要在时间与空间之间权衡。迄今为止讨论过的大多数算法中，增加