数据结构（其一）--基础知识篇

目录

1. 数据结构三要素

1.1 数据结构的运算

1.2 数据结构的存储结构

2. 数据类型，抽象数据类型

3. 算法

3.1 时间复杂度T(n)

3.2 空间复杂度

1. 数据结构三要素

1.1 数据结构的运算

即，增删改查

1.2 数据结构的存储结构

2. 数据类型，抽象数据类型

数据类型：

（1）. 原子类型：bool、int...

（2）. 结构类型：类、结构体...

抽象数据类型（ADT）：

类似于结构类型，使用者只需要知道该数据结构的名字以及其数据之间的联系（函数）即可

3. 算法

3.1 时间复杂度T(n)

时间复杂度越小，算法越优秀

（1）. 运算法规

加法：

多项相加的时候，只保留最高阶的项（次方）

T1(n) + T2(m) = T(max(n,m))

乘法：

T1 x T2 = O( f(n) x g(n) )

（2）. 常见的数量级比较

一般，记住前三个和后三个就足够使用——常对幂指阶 

3.2 空间复杂度

1GB = 1024*1024*1024 字节 约为10亿

1GB=1024MB   1MB=1024KB   1KB=1024字节

其实，不必知道各种数据类型的储存字节数，直接以个数储存就ok，毕竟到最后，系数都会被略去，化为系数为一的含 n 的计算公式。

在函数中，作为参数传入的数据都不必被算作空间复杂度的一部分，因为这些参数的数量是可知的，可知，即可被省略（递归函数除外）

在函数中，需要计算的是那些在函数中，声明产生的变量。

特别的：

在递归函数中，每次传入的数据，并不会覆盖在原来的位置，而是储存在新的地址，所以，欲求递归函数的空间复杂度，需要清楚，递归的有起点到终点的全过程内存占用情况。

在涉及到数组的递归函数时，尤其是数组的长度随递归发生改变，那么往往需要用到等差数列求和，