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

2024-07-12

1. 数据结构三要素

即，增删改查

数据类型：

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

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

抽象数据类型（ADT）：

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

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

（1）. 运算法规

加法：

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

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

乘法：

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

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

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

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

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

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

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

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

特别的：

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

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