信息学奥赛算法基础篇 (2).docx
版权申诉
114 浏览量
2023-03-07
20:28:35
上传
评论
收藏 323KB DOCX 举报
1
作者：avex79 出自：信息学奥赛辅导教育博客
学习过程序设计的人对算法这个词并不陌生，从广义上讲，算法是指为解决一个问题而
采用的方法和步骤；从程序计设的角度上讲，算法是指利用程序设计语言的各种语句，为解
决特定的问题而构成的各种逻辑组合。
我们在编写程序的过程就是在实施某种算法，因此程序设计的实质就是用计算机语言构
造解决问题的算法。算法是程序设计的灵魂，一个好的程序必须有一个好的算法，一个没有
有效算法的程序就像一个没有灵魂的躯体。
算法具有五个特征：
一个算法应包括有限的运算步骤，执行了有穷的操作后将终止运算，
不能是个死循环；
算法的每一步骤必须有确切的定义，读者理解时不会产生二义性。并
且，在任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。
如在算法中不允许有“计算 8/0”或“将 7 或 8 与 x 相加”之类的运算，因为前者的计算结果是
什么不清楚，而后者对于两种可能的运算应做哪一种也不知道。
3、输入：
一个算法有 0 个或多个输入，以描述运算对象的初始情况，所谓 0 个输入
是指算法本身定义了初始条件。如在 5 个数中找出最小的数，则有 5 个输入。
4、输出：
一个算法有一个或多个输出，以反映对输入数据加工后的结果，这是算法
设计的目的。它们是同输入有着某种特定关系的量。如上述在 5 个数中找出最小的数，它的
出输出为最小的数。如果一个程序没有输出，这个程序就毫无意义了；
算法中每一步运算应该是可行的。算法原则上能够精确地运行，而且
人能用笔和纸做有限次运算后即可完成。
一是看算法运行所占用的
时间
；我们用
时间复杂度
来衡量，例如：在以下 3 个程序中，
x:=x+1
含基本操作“x 增 1”的语句 x:=x+1 的出现的次数分别为 1，n 和 n
2
则这三个程序段的时
间复杂度分别为 O（1），O（n），O（n
2
），分别称为常量阶、线性阶和平方阶。在算法时间
复杂度的表示中，还有可能出现的有：对数阶 O(log n)，指数阶 O(2
n
)等。在 n 很大时，不
同数量级的时间复杂度有：O(1)< O(log n)<O(n)< O(nlog n)<O(n
2
) <O(n
3
) <O(2
n
)，很显然，
剩余32页未读，继续阅读
资源评论
