算法学习笔记之一 - 基本概念和术语介绍

2012-12-17 20:37

数据: 数据是信息的载体,是客观事物的符号表示,指能够输入到计算机中并被计算机程序处理的符号的总称。 在计算机科学中,数据就是计算机加工处理的对象,可以是数值数据,比如整数,实数等;也可以是非数值数据, 包括文字,图形,图像等。

数据元素: 是数据的基本单位。在不同的场合,数据元素又可被称为元素、节点等。

数据对象: 是具有相同性质的数据元素的集合,在某个具体问题中,数据元素都具有相同的性质, 属于同一数据对象。数据元素是数据对象的一个实例。

数据结构: 指相互之间存在着一种或多种特定关系的数据元素的集合。在任何问题中,数据元素之间都 不会是孤立的,在它们之间都存在着某种关系,这种数据元素之间的关系称为数据的逻辑结构,通常有 下列4种基本结构:

  • 集合结构: 数据元素属于同一个集合
  • 线性结构: 数据元素之间存在着一对一的关系
  • 树型结构: 数据元素之间存在着一对多的关系
  • 图状结构或网状结构: 数据元素之间存在这多对多的关系

数据的物理结构: 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型,它和数据的存储无关。 数据结构在计算机中的存放方式称为数据的物理结构,或称为存储结构,主要有4种,顺序存储、链式存储 、索引存储和散列存储。

数据结构的形式定义*: 一个数据结构有2个要素,1是数据元素的集合,2是关系的集合,在形式上, 数据结构通常采用一个二元组来表示:

data_structor = (D, R)

其中,D是数据元素的有限集,R是D上关系的有限集。

数据类型: 数据类型是一个值的集合和定义在这个集合上的一组操作的总称。数据类型显式或隐含的 规定了在程序执行期间变量或表达式所有可能的取值范围,以及在这个值上允许进行的操作。

抽象数据结构: 是指一个数学模型以及定义在该模型上一组操作的总称,可理解为对数据类型的进一 步抽象。
抽象数据类型可用一个三元组表示:

(D, S, P)

其中D是数据对象,S是D上的关系集,P是对D的基本操作集。

算法: 一种有限、确定、有效的并适合用计算机程序来实现的根据一定的输入得到一定的输出的解决 问题的方法。
算法和数据结构相辅相成,解决同一类型的问题可以用不同的数据结构,同一种数据结构也可以实现不同 的算法。根据问题的不同,算法可以很简单,也可以很复杂,选用哪个算法可能需要很复杂的数学分析。

算法分析: 用N表示问题的规模,算法的时间复杂度则表示为算法的运行时间怎样随着N的变化而变化。 算法的空间复杂度有时候也需要考虑。
时间复杂度一般有以下级别: 常数级别(1), 对数级别(log N), 线性级别(N), 线性对数级别(Nlog N), 平方级别(N*N), 立方级别(N*N*N), 指数级别(2*2*2...)。

常见的数据结构

常见的数据结构有数组(Array),堆栈(Stack),队列(Queue),链表(Linked List),树(Tree),图(Graph), 堆(Heap),散列(Hash)等,其中每一个还包含许多变种,比如链表又包含单向链表,双线链表,循环链表, 块状链表;树则包含二叉树,平衡二叉树,B树等;图则有有向图,无向图,连通图等等。

常见的算法

常见的算法则有排序算法,链表的顺序查找算法,数组的二分查找算法,图的广度优先遍历算法,深度 优先遍历算法,最短路径查找算法,字符串搜索算法,数据压缩算法等等。