学习目标
- 数组的概念和内存结构
- 数组常见操作的时间复杂度
- 数组与容器之间的区别
打卡
打卡day02:
今天学习: 数据结构与算法之数组
收获: 理解数组的内存结构特征以及其常见操作的时间复杂度.
数组
数组是一种线性表数组结构, 其拥有一块连续的内存空间, 并且存储相同类型的数据.
正因为数组拥有连续的内存空间, 且只存储相同类型的数据这两个特征, 所以:
- 当访问数组上任意数据的时间复杂度为O(1),
- 当删除数据时, 最好情况时间复杂度为O(1), 最坏情况时间复杂度为O(n), (加权)平均时间复杂度为O(n);
- 当添加数据时, 最好情况时间复杂度为O(1), 最坏情况时间复杂度为O(n), (加权)平均时间复杂度为O(n);
数组随机访问速度快, 增删元素速度慢.
数组与容器
在此仅以 Java 中的 ArrayList 作比较:
- ArrayList 不仅封装了数组的常用操作, 如添加或删除元素, 并支持动态扩容, 并提供丰富的操作, 更易于使用;
- 数组支持原始类型数据的存储, 而 ArrayList 并不支持, 且其自动装箱和自动开箱会消耗一定的性能, 所以使用数组时程序性能更好.