数据结构与算法.ppt

文档介绍：全国计算机等级考试二级教程公共基础知识
8/1/2017
1
第一章数据结构与算法
8/1/2017
2
算法
算法的基本概念
算法是指解题方案的准确而完整的描述。
算法不等于程序,也不等于计算方法。
一般说来,程序的编制不可能优于算法的设计。
8/1/2017
3
算法

可行性(effectiveness)
确定性(definiteness)
有穷性(finiteness)
拥有足够的情报
8/1/2017
4
算法
算法的定义:
是一组严禁地定义的运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下中止。
8/1/2017
5
算法

(1) 算法中对数据的运算和操作
算术运算
逻辑运算
关系运算
数据传输
8/1/2017
6
算法
(2) 算法的控制结构
算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具有传统流程图、N-S结构化流程图、算法描述语言等。
算法的基本控制结构:顺序、选择、循环
8/1/2017
7
算法

列举法
归纳法
递推
递归
减半递推技术
回溯法
8/1/2017
8
算法
例题1
设方程 f ( x ) = 0 在[ a , b ] 上有实根,且 f(a) 与 f(b) 异号,利用二分法来该方程在区间[ a , b ]上的一个实根。
a
b
c
b
c
8/1/2017
9
算法
算法复杂度
算法的复杂度包括时间复杂度和空间复杂度。

算法的时间复杂度是指算法所需要的计算工作量。
与问题有关
与问题的规模有关
与输入有关
8/1/2017
10