数据结构学习笔记（Ⅰ）：绪论

课程链接:【旧版】1.0_开篇_数据结构在学什么_哔哩哔哩_bilibili

目录

1 数据结构的基本概念

2 算法

2.1 算法的基本概念

1.算法概念

2.算法的特性

3.好算法特质

2.2 算法的时间复杂度

2.3 算法的空间复杂度

---

1 数据结构的基本概念

数据：能输入到计算机中并被程序识别和处理的符号的集合

数据元素：数据的基本单位，一个数据元素可由多个数据项组成

数据结构：相互之间存在一种或多种特定关系的数据元素的集合

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

数据结构三要素：逻辑结构、物理结构、数据的运算

逻辑结构：集合、线性结构、树形结构、图形结构

物理结构：如何用计算机表示数据元素的逻辑关系（顺序存储、链式存储、索引存储、散列存储）

数据的运算：施加在数据上的运算包括针对逻辑结构的运算的定义，针对存储结构的运算的实现

数据类型：一个值的集合和定义在此集合上的一组操作的总称（原子类型、结构类型）

抽象数据类型（ADT）：抽象数据组织及与之相关的操作

2 算法

2.1 算法的基本概念

1.算法概念

能够处理信息，解决实际问题

2.算法的特性

有穷性：算法必须是有穷的

确定性：相同的输入只能得到相同的输出

可行性：算法的操作可通过已实现的基本运算执行有限次实现

输入：一个算法有零或多个输入

输出：一个算法有一或多个输出

3.好算法特质

正确性、可读性、健壮性、高效率、低存储量

2.2 算法的时间复杂度

1.事先预估算法时间开销T(n)与问题规模n的关系 

2.常对幂指阶

3.通常考虑最坏时间复杂度与平均时间复杂度

2.3 算法的空间复杂度

空间复杂度 = 所占空间大小 / 递归调用的深度