ADT抽象数据类型
- 有两个重要特征:
- 数据抽象:用ADT描述程序处理的实体时,强调的是器本质的特征,其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)
- 数据封装: 将实体的外部特征和其内部实现细节分离,并且对外部用户隐藏起内部实现细节。
例如 抽象数据类型复数的定义:
ADT Complex:
数据对象:D = {e1, e2 | e1, e2 ∈ RealSet }
数据关系:R1 = {<e1, e2> | e1是复数的实数部分, | e2 是复数的虚数部分}
- 抽象数据类型的描述方法:
- 抽象数据类型可用(D,S,P)三元组表示:其中,D是数据对象,S是D上的关系集,P是对D的基本操作集。
算法和算法的衡量
- 算法:
- 算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要的特性:①有穷性 ② 确定性 ③ 可行性 ④ 有输入 ⑤ 有输出
1). 有穷性:对于任意一组合法输入值,在执行有穷步骤之后一定能结束,即:算法中的每个步骤都能在有限时间内完成;
2). 确定性:对于每种情况下所应执行的操作,在算法中都有确切的规定,使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下算法都只有一条执行路径;
3). 可行性:算法中的所有操作都必须足够基本,都可以通过已经实现的基本操作运算有限次实现之;
4). 有输入:作为算法加工对象的量值,通常提现为算法中的一组变量。有些输入量需要在算法执行过程中输入,而有的算法表面上可以没有输入,实际上已被嵌入算法之中;
5). 有输出:它是一组与“输入”有确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法的功能。
- 算法设计的原则
- 在设计算法时,通常应考虑达到以下目标:①正确性 ②可读性 ③健壮性 ④高效率与低存储量需求
1). 正确性:
首先,算法应当满足以特定的“规格说明”方式给出的需求。
其次,对算法是否“正确”的理解可以有以下四个层次:
a. 程序中不含语法错误;
b. 程序对与几组输入数据能够得出满足要求的结果;
c. 程序对于精心选择的、典型、苛刻且带有刁难性的机组输入数据能够得出满足要求的结果;
d. 程序对于一切合法的输入数据都能得出满足要求的结果;
通常以第c层意义的正确性作为衡量一个算法是否合格的标准。
2). 可读性:算法主要是为了人的阅读与交流,其次才是计算机执行。因此算法应该易于人的理解;另一方面,晦涩难读的程序易于隐藏较多错误而难以调试;
3). 健壮性:当输入的数据非法时,算法应当恰当地作出反映或进行相应处理,而不是产生莫名其妙的输出结果。并且,处理出错的方法不应是中断程序的执行,而应是返回一个表示错误或错误性质的值,以便在更高的抽象层次上进行处理。
4). 高效率与低存储量需求:通常,效率指的是算法执行的时间;存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。
-
算法效率的衡量方法和准则
通常有两种衡量算法效率的方法:1. 事后统计法:缺点:①必须执行程序 ②其他因素掩盖算法本质。2. 事前估计分析法。
- 和算法执行时间相关的因素:1. 算法选用的策略 2. 问题的规模 3. 编写程序的语言 4. 编译程序产生的机器代码的质量 5. 计算机执行指令的速度
网友评论