目录

一、数据结构概述

1、基本概念

2、数据结构

3、逻辑关系（线性结构&非线性结构）

4、物理结构（存储结构）

5、算法

6、算法特征

二、时空复杂度

1、时间复杂度

2、空间复杂度

3、结构类型

---

一、数据结构概述

1、基本概念

• 数据：能被计算机存储和识别的信息。文字、图形、视频、音频
• 数据结构：计算机存储数据和组织数据的方式

2、数据结构

• 数据的基本单位：数据元素（Data Elment）
• 数据的最小单位：数据项

1. 数据元素：由多个数据项组成。
2. 数据对象（Data Object）：多个数据元素的集合
3. 数据结构：描述多个数据之间的逻辑结构和物理结构。

• 逻辑结构：数据元素之间的逻辑关系
• 物理结构（存储结构）：计算机中存储数据的方式

3、逻辑关系（线性结构&非线性结构）

• 集合 （无关系）
• 线性结构（一对一)
• 树状结构（一对多)
• 图（多对多)

4、物理结构（存储结构）

• 顺序存储结构
• 链式存储结构

5、算法

        算法就是解决问题的步骤和方法。

6、算法特征

1. 有穷性：程序执行必须在有限次数内完成，每一次必须在有限时间内执行完成
2. 确定性：执行每一条语句都必须有准确的解释，不能出现二义性，意味着相同的输入就会有相同的输出
3. 可行性：程序中每一条复杂语句都可分解为基本指令，并且每一条基本指令都必须在有限时间内完成
4. 输入项：可以有一个或多个参数作为初始条件，然后对程序进行有效执行
5. 输出项：可以有一个或多个输出

总结：程序=数据结构+算法

二、时空复杂度

1、时间复杂度

1. 时间复杂度不是用算法的运行时间来衡量得
2. 时间复杂度指的是算法程序语句的执行次数，也称为语句频度。一般采用O()表示时间复杂度，采用T()表示程序语句的执行次数。

T(n)=O(n)+n;

采用估算值作为时间复杂度，即影响最大的一项，舍弃系数

计算技巧： 只需要计算出算法的基本执行语句的最高次项，并舍弃最高次项系数，使用O(xx)表示 如果没有使用n来表示规模，则计算出的是一个常数项，则时间复杂度O(1)

做题技巧

• 提到模块————耦合度
• 提到算法————复杂度

2、空间复杂度

• 程序在运行期间所占内存的空间大小叫做空间复杂度。
• 一个好的算法通常是执行时间短，占用空间少，并且可读性好、容易维护，易于移植到其他平台。

3、结构类型