文档介绍：全国计算机等级考试二级公共基础知识(基本数据结构与算法)
一. 基本数据结构与算法
重要知识点:
算法概念
算法复杂度
算法
算法(algorithm)基本概念
算法是指为解决某个特定问题而采取的确定且有限的步骤的一种描述,它是指令的有限序列,使得给定类型的问题通过有限的指令序列,在有限的时间内被求解,其中每一条指令表示一个或多个操作。
算法具有有穷性、确定性、可行性、输入和输出(拥有足够的情报)等5个基本特性。
[例1-1]在下列选项中,哪个不是一个算法一般应该具有的基本特征( )
A、确定性 B、可行性
C、无穷性 D、拥有足够的情报
答案:C
[解析]作为一个算法,一般应具有以下几个基本特征。
1、可行性
2、确定性
3、有穷性
4、拥有足够的情报
算法的基本要素
1、对数据对象的运算和操作
算术运算
逻辑运算
关系运算
数据传输
2、算法的控制结构
算法中各操作之间的执行顺序
描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等
一个算法一般可以用顺序、选择、循环三种基本机构组合而成。
算法设计基本方法
列举法
归纳法
递推
递归(以简洁的形式设计和描述算法)
减半递推技术
回溯法
算法设计的要求
正确性
可读性
健壮性
高效性
算法复杂度
时间复杂度
指算法运行从开始到结束所需要的计算工作量
一个算法是由控制结构(顺序、分支和循环)和原操作构成的,算法时间取决于两者的综合效果。
算法中基本操作重复执行次数n和算法执行时间同步增长,称作算法的时间复杂度。
算法的工作量=f(n),通常记作:T(n)=O(f(n))
例如:一个程序的实际执行时间为:
T(n)=++,则T(n)=O(n3),
通常用O(1)表示常数计算时间,常见的时间复杂度有:
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)
在实际问题中,算法的时间复杂度不仅与问题规模有关,而且还与特定的输入,也就是初始数据状态有关
[例1-2]算法的时间复杂度是指( )
A)执行算法程序所需要的时间
B)算法程序的长度
C)算法执行过程中所需要的基本运算次数
D)算法程序中的指令条数
答案:C
注意:2005年9月填空第2题,2006年9月选择第7题考查算法复杂度主要包括什么;2007年4月选择第1题考查时间复杂度的概念