请注意:本文编写于 2020-10-08,其中某些信息可能已经失去时效性。
数据是信息的载体,是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符合的集合。
数据大致可分为两类,一类是数值性数据,包括整数、浮点数、复数、双精度数等,主要用于工程和科学计算,以及商业事务处理;另一类是非数值性数据,主要包括字符和字符串,以及文字、图形、图像、语音等数据。
数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可以有若干个数据项组成,数据项是数据元素的不可分割的最小单位。例如:学生记录作为一个数据元素,它由学号、姓名、性别等数据项组成。
数据对象是具有相同性质的数据元素的集合,是数据的一个子集。
数据类型是一个值的集合和定义在此集合上一组操作的总称。
一个数学模型以及定义在该模型上的一组操作。
抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关,即不论其内部结构如何变化,只要它的数学特性不变,都不影响其外部的使用。通常用数据对象(D)、 数据关系(S)、基本操作集(P)这样的三元组来表示抽象数据类型。
数据结构包括三方面的内容:逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面,一个算法的设计取决于所选定的逻辑结构,而算法的实现依赖于所釆用的存储结构。
数据结构是由某一数据元素的集合和该集合中数据元素之间的关系组成的。
Data_Structure = {D, R}
D 是某一数据元素的集合,R 是该集合中所有数据元素之间的关系的有限集合。
有关数据结构的讨论主要涉及数据元素之间的关系,不涉及数据元素本身的内容。
数据的逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据,与数据的存储无关。
依据元素之间关系的不同,数据的逻辑结构分为两大类:线性结构和非线性结构。
线性结构:数据元素之间存在一对一的关系 树形结构:数据元素之间存在一对多的关系 图形结构:数据元素之间存在多对多的关系 集合结构:数据元素属于同一个集合
数据的存储结构是指数据结构在计算机中的具体表示(又称映像),也成物理结构。包括数据元素的表示和数据元素间关系的表示。数据的存储结构是数据的逻辑结构用计算机语言实现的。它依赖于计算机语言。主要有如下四种结构:
施加再数据上的运算包括运算的定义和实现。运算的定义时针对逻辑结构的,之处运算的功能;运算的实现是针对存储结构的,之处运算的具体操作步骤。
算法(algorithm)是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。
算法效率的度量可分为事前估计和后期测试。
一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记作 T(n)
,它是该算法问题规模 n
的函数,时间复杂度主要分析 T(n)
的数量级。算法中的基本运算(最深层循环内的语句)的频度与 T(n)
同数量级,所以通常釆用算法中基本运算的频度 f(n)
来分析算法的时间复杂度。因此,算法的时间复杂度也记为:
T(n)=O(f(n))
上式中 O
的含义是 T(n)
的数量级,其严格的数学定义是:若 T(n)
和 f(n)
是定义在正整数集合上的两个函数,则存在正常数 C
和 n_0
,使得当 n >= n_0
时,都满足 0 <= T(n) <= C * f(n)
。
注意:取 f(n)
中随 n
增长最快的项将其系数置为 1 作为时间复杂度的度量。例如,fi(n) = a * n^3 + b * n^2 + c * n
,则其时间复杂度为 O(n^3)
。
算法的时间复杂度不仅依赖于问题的规模 n
,也取决于待输入数据的性质(如输入数据元素的初始状态)。
一般总是考虑在最坏情况下的时间复杂度,以保证算法的运行时间不会比它更长。
在分析一个程序的时间复杂性时,有以下两条规则:
T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O( f(n) * g(n) )
常见的渐近时间复杂度有:O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
算法的空间复杂度 S(n)
,定义为该算法所耗费的存储空间,它是问题规模 n
的函数。渐近空间复杂度也常简称为空间复杂度,记作 S(n)=O(g(n))
。
一个上机程序除了需要存储空间来存放本身所用指令、常数、变量和输入数据外,也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间,若输入数据所占空间只取决于问题本身,和算法无关,则只需分析除输入和程序之外的额外空间。
算法原地工作是指算法所需辅助空间是常量,即 O(1)
。