1 / 115
文档名称:

全国计算机等级考试二级教程公共基础知识第一章_数据结....ppt

格式:ppt   页数:115页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

全国计算机等级考试二级教程公共基础知识第一章_数据结....ppt

上传人:你是我的全部 7/14/2013 文件大小:0 KB

下载得到文件列表

全国计算机等级考试二级教程公共基础知识第一章_数据结....ppt

文档介绍

文档介绍:2017/11/13
1
第一章数据结构与算法
数据结构与算法历年试题分数分布
2017/11/13
3
算法
算法的基本概念
算法是指解题方案的准确而完整的描述。
算法不等于程序,也不等于计算方法。
一般说来,程序的编制不可能优于算法的设计。
例如:操作系统是程序,不是算法
2017/11/13
4
算法
算法的定义:是一组严谨地定义的运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。
算法的基本特征:
可行性(effectiveness)
确定性(definiteness)
有穷性(finiteness)
拥有足够的情报
2017/11/13
5
算法

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

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

算法的时间复杂度是指算法所需要的计算工作量。
与问题有关
与问题的规模有关
与输入有关
算法工作量=f(n)n是问题的规模
程序里面主要考虑循环的执行次数
问题规模:输入量的多少。
基本语句:是执行次数与整个算法的执行次数成正比的操作指令。
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x++;
问题规模:n
基本语句:x++
算法
9
2017/11/13
10
课后****题选择1
算法的时间复杂度是指
执行算法程序所需要的时间
算法程序的长度
算法执行过程中所需要的基本运算次数
算法程序中的指令条数