[数据结构与算法]二、考研数据结构笔记——绪论（理解数据结构，算法，时间复杂度计算做题技巧）

一、数据结构基本概念

1、数据：数据是信息的载体。客观事物的一种表现形式。万事万物都能用数据表示出来。

2、数据元素：数据元素是数据的基本单位，一个数据元素有若干个数据项组成

3、数据项：构成数据元素的不可分割的最小单元。

理解：学java的可以这么理解，学生就是一个类，一个类里面有很多属性，比如学号，姓名和性别。
学生 = 类 = 数据元素
学号，姓名，性别=数据项。一个学生有多个数据项（学号，性别等等等）结合这个再读一遍概念就理解了.

4、数据对象：是具有相同性质的数据元素的集合，是数据对象的一个子集

理解，就是多个学生，多个相同的类 ，就是数据对象。

5、数据类型：是一个值的集合和定义在此集合上的一组操作的总称。主要分为：

• 原子类型：值不能再分。如int bool 等。
• 结构类型：值可以分解为若干个成分的数据类型。比如一个类，或者一个结构体
• 抽象数据类型：就是数据组织与之相关操作。

6、数据结构：相互之间存在一种或多种特定关系的数据元素的集合。主要包括三个方面：逻辑结构，存储结构和数据的运算。也就ADT。

理解：现在有很多数据元素（学生），我们要把这些数据元素（学生）的关系的逻辑结构（三角恋关系，谈恋爱关系，各种抽象的关系），存储结构（在班里是怎么坐座位的）和如何运算（对学生进行删除，查找，添加等）结合在一起就形成了数据结构。也就是讲数据结构，不仅有数据，而且还要有数据之间的关系以及数据怎么存的方式结合起来

二、数据结构三要素

上面已经有数据结构概念，三要素就是对概念进行提炼。三要素包括：逻辑结构，存储结构，数据运算。

• 逻辑结构：考试一般就两种线性结构和非线性结构。其中后面学的前几章都是线性结构（线性表，栈，队列，串，数组，广义表）。再往后都是非线性结构（树，图）
• 存储结构：考试一般重点分为顺序存储和链式存储。还有一些别的索引和散列。
• 数据运算：主要针对逻辑结构。说白了，就是增删查
• 总结：我们后面学的章节的开头，如，线性表，栈，队列，树，图都是学逻辑结构。而每个逻辑结构里面都有顺序存储方式和链式存储方式。这是理解数据结构的一条线。

三、算法

1、算法概念

对特定问题的求解步骤描述，指令是有限序列，主要有5个特征：

• 有穷性：步数和时间是有限的，不能没完没了。不能等人没了还没算出来。
• 确定性：每条指令都必须有含义，不能没意义。
• 可行性：对问题的描述能够转换为基本运算。
• 输入：有零个或多个输入。
• 输出：有一个或多个输出。

2、算法评价标准

一个好算法需要具备下面特点：

• 确定性：正确的解决问题
• 可读性：可以是伪代码，能读懂就OK。
• 健壮性：对特殊问题能进行处理，不能老报错。
• 效率和低存储量：时间要快，空间利用的要尽量小。也就是后面大家比较头疼的时间复杂度和空间复杂度。

3、时间复杂度

这个考试经常考，就是要用O(n)数量级把一个算法效率表示出来。

• 注意几点：
  • 取较高的阶数，小的忽略
    O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n的三次方) < O(2的n次方) < O(n!) < O(n的n次方)
    口诀：常对幂指阶

4、时间复杂度做题技巧

其实找规律就行，举几个例子：

5、空间复杂度

完全可以用空间来换取时间，这个考的很少，一般记一些常用查找排序用的空间复杂度，，考试可能会考。

下一章：考研数据结构笔记——线性表（顺序表和链表必背代码及混淆点）