【数据结构】P1 数据结构是什么、算法怎样度量

1.1 基本概念与术语

• 数据： 数据是信息的载体，是所有能被计算机识别以及处理的符号。
• 数据元素： 数据元素是数据基本单位，由若干 数据项 组成，数据项是构成数据元素最小的单位。
  • $e.g.$ 数据元素如一条学生记录，数据项则为其中学号、姓名、性别等属性；
• 数据对象： 数据对象是具有相同性质的数据元素的集合。
  • $e.g.$ 小明是班级1学生，小红也是班级1学生，有集合 $班级1=小明,小红,....$
• 数据类型： 分为原子类型、结构类型以及抽象数据类型；
  • 原子类型： 其值不可再分的数据类型；
  • 结构类型： 其值可以再分解为若干成分的数据类型；
  • 抽象数据类型
• 数据结构： 数据结构描述数据元素相互之间的关系，包括三方面内容：逻辑结构、存储结构和数据的运算。

---

1.2 数据结构三要素

数据结构的三要素为：逻辑结构、存储结构、数据的运算；

1.2.1 逻辑结构

逻辑结构指数据元素之间的逻辑关系，从逻辑关系上描述数据，分为线性结构与非线性结构。

线性表是典型的线性结构，树和图是典型的非线性结构。

1.2.2 存储结构

存储结构指数据结构在计算机中的表示，也称物理结构，是用计算机实际实现的逻辑结构，主要有顺序存储、链式存储、索引存储和散列存储。

• 顺序存储：逻辑上相邻的元素存储在物理位置也相邻的存储单元中。
  • 优点：可以实现随机存取，每个元素占用最小的存储空间。
  • 缺点：只能使用相邻的一整块存储单元，会导致出现较多的外部碎片。
• 链式存储： 不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储位置的指针来表示元素之间的逻辑关系。
  • 优点：不会出现外部碎片，能充分利用全部存储单元。
  • 缺点：存储指针会额外占用存储空间，且只能顺序存取。
• 索引存储： 另建立索引表，其中每一项为索引项，一般形式为：关键字、地址。
  • 优点：检索速度快。
  • 缺点：索引表额外占用存储空间，且增加、删除数据时也需修改索引表的时间成本。
• 散列存储： 根据元素的关键字计算该元素的存储地址，又称为哈希存储。
  • 优点：检索、增加和删除结点操作快。
  • 缺点：若散列函数不好，会导致存储单元冲突，解决冲突需要额外的时间和空间开销。

1.2.3 数据的运算

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

• 运算的定义 是针对逻辑结构的，指出运算的功能。
• 运算的实现 是针对存储结构的，指出运算的步骤。

---

2.1 算法定义

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

2.2 算法五大特征

• 有穷性： 一个算法必须在执行有穷步骤之后结束，且每一步都在有穷时间内完成。
• 确定性： 算法中每条指令必须有明确的含义，对于相同的输入只能得出相同的输出。
• 可行性： 算法中操作可以通过已经实现的基本运算执行有限次来实现。
• 输入： 一个算法有零个或者多个输入。
• 输出： 一个算法有一个或者多个输出。

一个好的算法，通常应考虑如下目标：

• 正确性： 算法应能正确的解决问题。
• 可读性： 算法应具有良好的可读性，简单的结构，同时带有标注帮助人们理解。
• 健壮性： 输入非法数据时，算法应能对其做出反应和处理，而不会意外退出或者输出莫名结果。
• 高效率与低存储量： 效率是指算法执行的时间，存储量是指算法执行中所需的最大存储空间。

2.3 算法效率度量

2.3.1 时间复杂度

一个语句的频度指的是该语句在算法中被重复执行的次数。算法中所有语句的频度之和为 $T(n)$，时间复杂度分析 $T(n)$ 的数量级。

算法的时间复杂度记为：$T(n)=O(f(n))$
其中 $O$ 的含义表示数量级。

需要注意的是，算法的时间复杂度不仅仅取决于算法的结构规模，还取决于待输入数据的初始状态。对于同一个算法，因初始状态不同，结果可以为 $O(n)$ 也可能为 $O(1)$。
其中 $O(n)$ 我们其为 “最坏时间复杂度”，$O(1)$ 称为 “最好时间复杂度”，而 “平均时间复杂度” 则为当所有可能输入实例在等概率出现的情况下，算法的期望运行时间。

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

1. 加法规则：
   $$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$$

2. 乘法规则：
   $$T(n)=T_1(n)\ast T_2(n)=O(f(n))\ast O(g(n))=O(f(n)\ast g(n))$$

常见的渐进时间复杂度为：
$$O(1)<O(lo{g}_{2}n)<O(n)<O(nlo{g}_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$

---

2.3.2 空间复杂度

算法的空间复杂度 $S(n)$ 为该算法所耗费的存储空间，记为 $S(n)=O(g(n))$

一个程序执行时除需要存储空间来存放本身的指令、常数、变量和输入数据外，还需要一些数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。

算法原地工作是指算法所需的辅助空间为常量，即为 $O(1)$。