需要掌握：时间复杂度的定义与计算
介绍
顺序表，也称为顺序存储。用 数组存储数据，数组的 内存是连续分配的，静态分配的
特点
- 物理存储：元素在内存中是 连续排列 的，地址相邻；
- 逻辑与物理：逻辑上的先后顺序（比如第1个、第2个元素）和物理存储顺序完全一致；
- 索引访问：可以通过 下标（索引） 直接计算出元素的内存地址，实现 随机访问。
优点
读数据快
缺点
在使用数组之前需要确定空间的大小，灵活性差
除了读数据外，其他操作效率低
访问元素的时间复杂度
根据索引读取，所以是 1
时间复杂度：O(1)
根据值查询的时间复杂度
最好的情况
查找第一个元素，所以是 1
最坏的情况
查找最后一个元素，所以是 n
平均是
(1+n)/2，大O表示法：O(n)
插入元素，需移动元素的数量
最好的情况
在末尾插入元素，不需要移动，所以是 0
最坏的情况
插入第一个位置，那么原来的 n 个元素都要向后移动，所以是 n
平均
平均是：n/2
时间复杂度
O(n)
解释：对于时间复杂度来说，O(n/2)就是 O(n)
删除元素，移动元素的数量
最好的情况
删除最后一个元素，不需要移动，所以是 0
最坏的情况
删除第一个元素，那么原来的 n-1 个元素都要向前移动，所以是 n-1
平均
(n-1)/2
时间复杂度
O(n)
解释：当 n 无限大时，(n-1)/2 就是 n/2 ，对于时间复杂度来说，O(n/2)就是 O(n)