当前位置:文档之家› 第二章 算法分析基础

第二章 算法分析基础

其中评价算法的三条主要标准是:
(1) 算法实现所耗费的时间; (2) 算法实现所所耗费的存储空间,其中
主要考虑辅助存储空间; (3) 算法应易于理解,易于编码,易于调
试等等。
2.1.2 算法的时间复杂性
1.和算法执行时间相关的因素:
1)问题中数据存储的数据结构 2)算法采用的数学模型 3)算法设计的策略 4)问题的规模 5)实现算法的程序设计语言 6)编译算法产生的机器代码的质量 7)计算机执行指令的速度
上节
下节
【例1】求n!
递归方程为: T(n)=T(n-1)+O(1) 其中O(1)为一次乘法操作.
迭代求解过程如下:
T(n)=T(n-2)+O(1)+O(1) =T(n-3)+O(1)+O(1)+O(1) …… =O(1)+……+O(1)+O(1)+O(1) =n*O(1) =O(n)
【例2】抽象地考虑以下复杂一点的递归方程,且假设
最有实际价值的,是最坏情况下的时间复杂性。
2.1.3 算法的空间复杂性
算法的存储量包括:
1) 输入数据所占空间:取决于问题本身,与算法无关 2) 算法本身所占空间:相对固定 3) 辅助变量所占空间
研究算法的空间效率, 只需要分析除输入和算法之 外的额外空间。 若所需额外空间相对于输入数据量来 说是常数,则称此算法为原地工作, 否则,它应当是规模 的一个函数。
一具体算法的时间复杂度和空间复杂度往往是不独立的, 在算法设计中要在时间效率和空间效率之间折衷。
2.2.1 非递归算法分析
1.仅依赖于问题规模的时间复杂度
有一类简单的问题,其操作具有普遍性,也就是说对所 有的数据均等价地进行处理,这类算法的时间复杂度,很 容易分析。
【例1】交换i和j的内容。
Temp=i;i=j;j=temp;
NP问题:至今没有找到多项式时间算法解的一类问题,可以 在多项式时间内验证一个解是否正确的问题,亦称为易验 证问题类。
NP完全问题(NPC问题,C代表complete):从NP类的问题 中分出复杂性最高的一个子类。
•如果一个NPC问题存在多项式时间的算法,则所有的NP 问题都可以在多项式时间内求解,即P=NP成立!! •要么每个NP完全问题都存在多项式时间的算法(即通常 所指的有效算法);要么所有NP完全问题都不存在多项 式时间的算法。
数量级相等是这样定义的,设f(n)是一个关于正整数n 的函数,若存在一个常数C,使
则称f(n)与g(n)是同数量级的函数。
算法(渐进)时间复杂度,一般均表示为以下几种数量级的形式 (n为问题的规模,c为一常量):
Ο(1)称为常数级 Ο(logn)称为对数级 Ο(n)称为线性级 Ο(nc)称为多项式级
若对于查找不同元素的概率P不相同时,其算法复杂 度就只能做近似分析,或在构造更好的算法或存储结构后, 做较准确的分析。
上节
下节
2.2.2 递归算法分析
【例1】求N!
构造算法中的两个步骤:
1)N!=N*(N-1)!
2)0!=1, 1!=1。
递归算法如下:
以n=3为例,调用过程如下:
fact(3)-fact(2)-fact(1)-fact(2)-fact(3)
y++
上节
下节
【例3】循环次数间接依赖规模n
(1) x=1; (2) for(i=1;i<=n;i++) (3) for( j=1;j<=i;j++) (4) for(k=1;k<=j;k++) (5) x++; 该算法段中频度最大的语句是(5),从内层循环向外层分析 语句(5)的执行次数:
则该算法段的时间复杂度为:T(n)=O(n3 /6+低次项)= O(n3)。
2.提高效率。
1)以提高算法的全局效率为主,提高局部效率为辅。 2)在优化算法的效率时,应当先找出限制效率的“瓶颈”。 3)多数情况下,时间效率和空间效率可能是对立的,此时
应当分析哪个更重要,作出适当的折衷。 4)可以考虑先选取合适的数据结构,再优化算法。 5)递归过程的实现决定了递归算法的效率往往很低,费
以上三条单个语句的频度均为1,该算法段的执行时间 是一个与问题规模n无关的常数。算法的时间复杂度为常 数阶,记作T(n)=Ο(1)。
如果算法的执行时间不随着问题规模n的增加而增长, 即使算法中有上千条语句,其执行时间也不过是一个较大的 常数。此类算法的时间复杂度是Ο(1)。
上节
下节
【例2】循环次数直接依赖规模n
2.算法的时间复杂度还与输入实例的初始状态有关。
这类算法的时间复杂度的分析比较复杂,一般分最好情 况(处理最少的情况),最坏情况(处理最多的情况)和平均情 况分别进行讨论。
【例4】
【例4】在数值A[0..n-1]中查找给定值K的算法大 致如下:
(1) i=n-1; (2) while( i>=0 and A[i]<>k ) (3) i=i-1; (4) return i;
Ο(cn)称此为指数级
Ο(n!)称为阶乘级
以上时间复杂度级别是由低到高排列的,其随规模n的增长 率,由图2-1可见一斑:
图2-1 T(n)与规模n的函数关系
原则上一个算法的时间复杂度, 最好不要采用指数级和阶 乘级的算法, 而应尽可能选用多项式级或线性级等时间复 杂度级别较小的算法。
对于较复杂的算法,可将它分隔成容易估算的几个部分, 然后再利用“O"的求和原则得到整个算法的时间复杂度。
度量标准:
一.计算所需的步数或指令条数(这叫时间复杂度)。 二.计算所需的存储单元数量(这叫空间复杂度)。
上节
下节
问题的复杂性和算法的复杂性的区别: 只就时间复杂性说,算法的复杂性是指解决问题
的一个具体的算法的执行时间,这是算法的性质; 问题的复杂性是指这个问题本身的复杂程度。
P类问题:就是所有复杂度为多项式时间的问题的集 合(易解的问题类,否则为难解的问题)。 例如:梵塔问题 推销员旅行问题等
第二章 算法分析基础
2.1 算法分析体系及计量
算法分析的任务: 对设计出的每一个具体的算法,利用数
学工具,讨论其复杂度。
2.1.1 算法分析的评价体系
对算法的评价有两个大的方面:
一.对算法的维护的方便性。
二.算法在实现运行时占有的机器资源 的多少,即算法的运行的时间和空间效率。
对算法的分析和评价,一般应考虑正确性、可 维护性、可读性、运算量及占用存储空间等诸多 因素。
时和费内存空间。在解决问题时,如果能使用递推法 解决的,应考虑用递推法,其效率更高些。 6)注意多用数学方法,可以大大提高算法效率。 7)另外还有一些细节上的问题,如:乘、除运算的效率比 加、减法运算低。
例:若算法的两个部分的时间复杂度分别为 T1(n)=O(f(n)) 和 T2(n)=O(g(n)),
则总的时间复杂度为: T(n)=T1(n)+.问题时间复杂度的上界和下界

5.算法时间复杂度的最好情况和最坏情况
我们要确定能反映出算法在各种情况下工作的数据集, 选取的数据要能够反映、代表各种计算情况下的估算, 包 括 最好情况下的时间复杂度(Tmax) 最坏情况下的时间复杂度(Tmin) 平均情况下的时间复杂度(Tavg)
前,一定要有确切的含义,或是被赋值或是经模块接口 传递信息。 3)算法中要当心变量发生上溢或下溢,数组的下标越界。 4)写算法时就要考虑,可能出现错误的情况,提示执行错 误处理算法。 5)编写算法时区别问题的循环条件和停止条件,不要误用。 6)注意算法中循环体,或条件体的内容,不要误把循环体 内的操作写互循环体外或者出现相反的错误。
算法的空间复杂度是指算法在执行过程中所占辅助 存储空间的大小用S(n)表示。 算法的空间复杂度S(n)也可表示为:
S(n)=Ο(g(n)) 表示随着问题规模n的增大, 算法运行所需存储量的增 长率与g(n)的增长率相同。
2.1.4 NP完全问题
NP完全性问题:属于“计算复杂性”研究的课题。 计算复杂性:就是用计算机求解问题的难易程度。
3.时间复杂度估算
因为: 算法=控制结构+原操作(固有数据类型的操作)
所以:
算法的执行时间= 原 操作的执行次数*原操作的执行时间
语句的频度指的是该语句重复执行的次数。
一个算法转换为算法后所耗费的时间,除了与所用的计算软、 硬件环境有关外,主要取决于算法中指令重复执行的次数,即语 句的频度相关。
一个算法中所有语句的频度之和构成了该算法的 运行时间。
此算法的频度不仅与问题规模n有关,还与输入实 例中A的各元素取值及k的取值有关:
1. 若A中没有与k相等的元素,则语句(2)的频度 f(n)=n;这是最坏情况。
2. 若A的最后一个元素等于k,则语句(2)的频度f(n) 是常数1;这是最好情况。
在求平均情况时,一般地假设查找不同元素的概率P是 相同的,则算法的平均复杂度为:
例如:
for( j=1;j<=n;++j) for(k=1;k<=n;++k)
++x;
语句“++x、k<=n、++k”的频度是n2, 语句“ j=1、k=1”的频度是1, 语句“j<=n;++j”的频度是n。 算法运行时间为:3*n2+2n+2。
经常从算法中选取一种对于所研究的问题来说是基本(或者 说是主要) 的原操作,以该基本操作在算法中重复执行的次数作 为算法运行时间的衡量准则。这个原操作,多数情况下是最深层 次循环体内的语句中的原操作。
(1) x=0;=0; (2) for(k-1;<=n;++) (3) x++; (4) for(i=1;<=n;++) (5) for( j=1;j<=n;++) (6) y++;
相关主题