数据结构与算法笔记cp1：基本概念

1.数据结构

1.1 基本概念：

• 数据元素：也称为记录，是数据的基本单位。比如把动物看作数据，那么数据元素指的就是牛、羊、马等。
• 数据项：这是数据的最小单位，多个数据项构成了一个数据元素。比如把牛看作数据元素，那么数据项指的就是牛的年龄、体态等。
• 数据对象：这是数据的子集，表示性质相同的数据元素的集合。所谓性质相同，指的是各数据元素之间有相同数目和类型的数据项。
• 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。结构，指的就是这些元素互相之间的关系，这是重点。

1.2 分类：

• 逻辑结构（思路）： 从广义上分为线性结构和非线性结构。
  • 非线性结构：集合（同在一块）、树（一对多）、图（多对多）；
  • 线性结构：表、栈、队列、串、数组

• 物理/存储结构（实现）：
  • 顺序存储结构
  • 链接存储结构
  • 索引存储结构
  • 散列存储结构

1.3 抽象数据类型 ADT

ADT 即 Abstract data type，抽象数据类型的三个主体是数据对象 + 关系 + 操作。 我们可以用下面的格式描述抽象数据类型：

ADT 抽象数据类型名{ 数据对象：it is..... 数据关系：they are..... 基本操作： 操作1：done sth.... 初始条件：.... 操作结果：.... 操作2：done sth.... 初始条件：.... 操作结果：.... } ADT 抽象数据类型名

2.算法

2.1 基本特性：

有穷性（时间有穷、步骤有穷）、确定性（没有歧义）、可行性、输入、输出

2.2 优劣标准：

正确性（至少可以得到正确结果，对于非法输入也应有提示）、可读性、健壮性、高效性（时间 + 空间）

2.3 时间复杂度

• 一个算法的执行总时间应该等于每条语句执行时间之和，假定执行时间都为单位 1，那么则等于语句总数，同时我们只考虑耗时长的操作语句 —— 即基本操作语句，那么基本操作语句的执行次数（语句频度）就可以在某种关系上反映算法的执行总时间。
• 大 O 表示法： 给定问题规模 n 以及关于 n 的函数 f(n)，其中，f(n) 代表基本语句执行次数。那么，时间复杂度 T(n) = O(f(n))，它表示随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同。
• 大 O 阶推导（分析时间复杂度）：
  • 找出语句频度最高的基本语句；
  • 基于该语句的频度推导出对应的 f(n)；
  • 取 f(n) 的数量级得到最终的 f(n)。这意味着允许我们忽略低次幂和最高次幂的系数。
• 经过大 O 阶推导，可以得到常数阶、平方阶、对数阶等。需要注意的是，当算法可以在常数时间内完成时（与问题规模无关），其时间复杂度依然是常数阶 O(1)。

2.4 空间复杂度

• 空间复杂度 S(n)=O(f(n))，其中，n 为问题规模，f(n) 表示关于 n 所占存储空间的函数。
• 若算法执行时所需的辅助空间相对于问题规模来说是一个常数，则称此算法为原地工作，空间复杂度为 O(1)。也就是说，不管我问题规模多大，所需要的辅助空间始终是固定的。比如下面两个算法：

//算法1
for(i = 0;i < n/2;i++){
  t = a[i];
  a[i] = a[n-i-1];
  a[n-i-1] = t;
}

//算法2
for(i = 0;i < n;i++)
  b[i] = a[n-i-1];
for(i = 0;i < n;i++)
  a[i] = b[i];

对于算法1，不管问题规模多大，总是只需要一个临时变量 t 暂存值即可，因此其空间复杂度为 O(1)；对于算法2，采用的是逆序输出原数组到新数组中，之后再覆盖原数组，很显然，随着 n 的增大，新数组要求的存储空间也要增大，所以其空间复杂度为 O(n)。