请选择 进入手机版 | 继续访问电脑版

智少年IT小达人_演武台

 找回密码
 立即注册
查看: 3552|回复: 0

全国青少年信息学奥林匹克联赛入门 - 算法复杂度

[复制链接]
本站粉丝  发表于 2015-7-6 15:26:07 |阅读模式
如何来评价一个算法的好坏呢?主要是从两个方面:
一是看算法运行所占用的时间;我们用时间复杂度来衡量,例如:在以下3个程序中,
(1)x:=x+1
(2)for i:=1 to n do
x:=x+1
(3)for i:=1 to n do
       for j:=1 to n do
          x:=x+1
含基本操作“x增1”的语句x:=x+1的出现的次数分别为1,n和n2则这三个程序段的时间复杂度分别为O(1),O(n),O(n2),分别称为常量阶、线性阶和平方阶。在算法时间复杂度的表示中,还有可能出现的有:对数阶O(log n),指数阶O(2n)等。在n很大时,不同数量级的时间复杂度有:O(1)< O(log n)<O(n)< O(nlog n)<O(n2) <O(n3) <O(2n),很显然,指数阶的算法不是一个好的算法。

二是看算法运行时所占用的空间,即空间复杂度。 由于当今计算机硬件技术发展很快,程序所能支配的自由空间一般比较充分,所以空间复杂度就不如时间复杂度那么重要了,有许多问题人们主要是研究其算法的时间复杂度,而很少讨论它的空间耗费。

时间复杂性和空间复杂性在一定条件下是可以相互转化的。在中学生信息学奥赛中,对程序的运行时间作出了严格的限制,如果运行时间超出了限定就会判错,因此在设计算法时首先要考虑的是时间因素,必要时可以以牺牲空间来换取时间,动态规划法就是一种以牺牲空间换取时间的有效算法。对于空间因素,视题目的要求而定,一般可以不作太多的考虑。
回复

使用道具

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|智少年 ( 粤ICP备15046784号

GMT+8, 2022-10-1 09:50 , Processed in 0.111480 second(s), 17 queries .

© 2015-2018 深圳智少年教育咨询有限公司

快速回复 返回顶部 返回列表