三九 Study Notes

Appearance

绪论 ​

第一节 基本概述 ​

数据结构的组成部分：

  1. 逻辑结构（内在关系）
  2. 存储（物理）结构（存放形式）
  3. 对数据的运算（删除，插入，查找，修改，排序）

数据：在计算机科学中指所有能输入到计算机中并被计算机陈旭处理的符号总称。例如，整数、实数和字符串都是数据。

数据元素：数据元数是数据的基本单位，也称节点或记录。

数据项：数据项是数据处理中的最小单位，是数据记录的基本单位，不可分的数据单位。

数据对象：数据对象是性质相同的数据元素的集合，是数据的子集。

大小关系：数据 > 对象 > 元素 > 项

数据结构 (D,R)/(D,S)：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据的逻辑结构：数据的逻辑结构是对数据元素之间逻辑关系的描述。它与数据的存储无关，是独立于计算机的。主要分为两类：线性结构和非线性结构，其中集合、图、树形结构数据非线性结构。

  1. 线性结构：结构中的数据元素之间存在一对一的关系。
  2. 集合：结构中的数据元素除了同属于一种类型外，别无其他关系。
  3. 树形结构：结构中数据元素之间存在一对多的关系。
  4. 图状结构（网状结构）：结构中元素之间存在多对多的关系。

数据的存储结构：存储结构又称物理结构（依赖计算机）是数据结构在计算机中的实际表示方式，它包含对数据元素的表示和对关系的表示

  1. 顺序存储：节点之间的逻辑关系由存储单元的相邻位置体现，通常借助程序语言的数组类型来描述。其优点是存储密度大，可实现随机存取。（主要用于查找）
  2. 链式存储：不要求逻辑上相邻的节点在存储位置上相邻，结点之间的逻辑关系是由附加的结点指针来反映。（主要用于插入，删除）
  3. 索引存储（分块）：索引存储方法在存储结点信息时除建立存储结点信息外，还建立附加的索引来标识节点地址。
  4. 散列存储（哈希）：根据结点的关键字通过散列函数直接计算出该结点的存储地址，这种存储方法本质上是顺序存储方法的扩展。

第二节 数据类型与抽象数据类型（ADT） ​

数据类型分类：

  1. 原子类型
  2. 结构类型（数组，广义表）

数据类型：数据类型是一个值的集合和定义在这个值集合上的一组操作的总称。整形（int）、实型（即浮点型 float）、字符型（char）等基本类型。

抽象数据（定义取决与逻辑结构）类型：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。

ADT 抽象数据类型名：

  1. 数据对象（数据集）D
  2. 数据关系（结构集）S
  3. 基本操作 P

抽象数据类型作用：能独立定义数据结构，是高级的数据类型。

第三节 算法 ​

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

程序的定义：用某种程序设计语言对算法进行具体实现（程序 = 数据结构 + 算法）

算法的特性：

  1. 有穷性：一个算法必须保证执行有限步之后结束且每一步必须在有穷时间内完成。
  2. 确定性：算法的每一步骤必须有确定的定义，不会产生二义性。
  3. 可行性：算法中的所有操作都必须可以通过已经实现的基本操作进行运算，并在有限次内实现，且人们用笔和纸做有限次运算后也可以完成。
  4. 输入性：一个算法有0个或者多个输入，以刻画运算对象的初始情况，所谓的 0 个输入是指算法本身确定了初始条件。
  5. 输出性：一个算法有一个或者多个输出，以反映对输入数据加工后的结果。

算法设计的基本要求：

  1. 正确性：要求算法能够正确地执行预先规定的功能和性能要求，这是最重要也是最基本的标准。
  2. 可读性：要求算法易于让人理解。
  3. 健壮性：要求算法有很好的容错性，能够对不合理的数据进行检查。
  4. 高效性（时间）与低存储量（空间）需求：算法的效率主要是指算法的执行时间，对于同一个问题如果有多种算法可以求解，执行时间短的算法效率高，算法的存储量是指算法执行过程中所需要的最大量储存空间。高效率和低存储量这两者都与问题规模有关，且是衡量算法好坏的两个重要指标。

第四节 时间复杂度 ​

算法效率分析的目的是看算法实际是否可行，并在同一问题存在多个算法时，可进行时间和空间性能上的比较，以便从中挑选出较优算法。

衡量算法的方法有两种：事后统计和事前分析估算法，事后统计法需要先将算法实现，然后在测量其时间和空间开销，会有缺陷。所以我们一般采用的是事前分析估算法，计算算法的时间复杂度和空间复杂度来衡量算法的效率。

问题规模（n 输入量的大小）：问题规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用证书 n 表示。

语句频度（ f(n)语句执行次数 ）：一条语句的重复执行次数称作语句频度，一个算法执行时间可用该算法中所有语句频度之间和 f(n) 来度量。

时间复杂度：O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

求时间复杂度总结：

  1. 程序执行次数为常数 O(1)
  2. 对于一个 for：增量为 ++/-- 时间复杂度与未知数有关。增量为 i = i * a 时间复杂度为对数阶，乘谁以谁为底。O(logan)
  3. 对于多个循环：每一个循环的执行次数相乘 = f(n)

【案例 1】题型已知语句频度时间复杂度 f(n) = 2n3 + 4n2 + 100

步骤：

  1. 留最大项，常数为 O(1)
  2. 去系数
  3. f(n) = 2n3 + 4n2 + 100 => 2n3 => O(n3)

【案例 2】假设时间复杂度为 O(n2) 的算法在有 200 个元素的数组上运行需要 3.1ms，则在有 400 个元素的数组上运行需要 12.4 ms。

分析：

  1. 已知 n = 200 => O(n2) => 3.1 => (200)2 => 3.1
  2. n = 400 => (400)2 => (200*200)2 => 4 * (200)2 => 4 * 3.1 => 12.4

第五节 空间复杂度 ​

算法的控价复杂度 O(n)，定义为该算法所耗费的存储空间，一个程序除了需要存储空间来存放本身所用数据外，也需要一些对数据进行操作的工作单元和存储一些为计算所需的辅助空间。算法原地工作是指算法所需辅助空间是常量，即 O(1).