1 数据结构与算法的基本概念

第一节数据结构

1 数据

数据是信息的载体，是所有能输入到计算机中并被计算机程序识别和处理的符号的集合，用于描述客观事物的属性。

2 数据元素

数据元素是数据的基本单位。一个数据元素可以由若干数据项组成。数据项是构成数据元素的不可分割的最小单位。

例如，一个学生的信息可以作为一个数据元素，而该学生的学号、姓名、性别等各自可作为一个数据项。

3 数据结构

我们将一批数据看成一个整体。逻辑上，这些数据之间存在着某种关系；实际存储上，这些数据在计算中的存储位置也存在着某种关系；我们在这些数据上定义一些运算，可以对其进行操作。

数据结构包括3个方面的内容：

3.1 逻辑结构

逻辑结构是指数据元素之间的逻辑关系，包括集合结构（一对零）、线性结构（一对一）、树形结构（一对多）和图状结构（多对多）等。

3.2 存储结构

存储结构是指数据结构在计算机中的存储形式，包括顺序存储、链式存储、索引存储和散列存储等。

3.2.1 顺序存储

逻辑上相邻的元素，它们的物理存储位置也相邻。

优点：可以实现随机存取。

缺点：只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片；对数据的添加和删除开销较大。

3.2.2 链式存储

逻辑上相邻的元素，它们的物理存储位置不一定相邻，而是在元素中额外存储相邻元素的地址信息，以实现逻辑关系。

优点：充分利用存储单元，不会出现碎片；对数据的添加和删除开销小。

缺点：需占用额外的存储空间；对数据的查找开销较大。

3.2.3 索引存储

在存储元素信息的同时，还建立附加的索引表（相当于目录）。

优点：对数据的查找较快。

缺点：需占用额外的存储空间；增加和删除数据时需要修改索引表，开销较大。

3.2.4 散列存储

根据元素的关键字确定该元素的存储地址。

优点：检索、增加和删除元素的操作都很快。

缺点：若散列函数不好，可能会出现元素存储单元的冲突，为了解决冲突会增加时间和空间开销。

3.3 运算

施加在数据上的运算包括运算的定义和实现。

运算的定义是针对逻辑结构的，指出运算的功能。

运算的实现是针对存储结构的，指出运算的具体操作步骤。

第二节算法

1 算法

算法是对特定问题进行求解的步骤的描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。

2 算法的特性

算法具有下列5个重要特性。

2.1 有穷性

一个算法（对任何合法的输入值）必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。

2.2 确定性

算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。

2.3 可行性

算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

2.4 输入

一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。

2.5 输出

一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

3 算法效率的度量

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

3.1 时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数。

算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数。由于随着n的增大，函数T(n)中的常数项、低次项以及系数对其影响不大，因此我们主要分析T(n)的数量级。

算法的时间复杂度记为：T(n)=O(f(n))。其严格的数学定义是：若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正常数C和n₀，使得当n≥n₀时，都满足0≤T(n)≤Cf(n)。

最坏时间复杂度：在最坏情况下，算法的时间复杂度。

平均时间复杂度：所有可能输入实例在等概率出现的情况下，算法的期望运行时间。

最好时间复杂度：在最好情况下，算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

在分析一个程序的时间复杂性时，有以下两条规则：

(1)加法规则：T(n)=T₁(n)+T₂(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

(2)乘法规则：T(n)=T₁(n)×T₂(n)=O(f(n))×O(g(n))=O(f(n)×g(n))

常见的渐进时间复杂度为：O(1)<O(log₂n)【while循环】<O(n)【for循环】<O(nlog₂n)【while循环与for相互嵌套】<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

3.2 空间复杂度

算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。