一,如何实现随机访问?
数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。数组的两个特点是:
- 线性表
- 连续的内存空间和相同类型的数据(随机访问)
计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:
a[i]_address = base_address + i * data_type_size // 如果数组从 1 开始计数 a[k]_address = base_address + (k-1)*type_size 复制代码
数组从
1
开始编号,是因为根据寻址公式,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。
注意:数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)O(1)O(1),但找的时间复杂度并不为 O(1)O(1)O(1)。,毕竟即便是排好序的数组,用二分查找,时间复杂度也是 O(logn)O(logn)O(logn)。
这点很多博客没有注明。
二,低效的“插入”和“删除”
假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。平均情况时间复杂度为 (1+2+...n)/n=O(n)(1+2+...n)/n=O(n)(1+2+...n)/n=O(n)。
三,容器能否完全替代数组?
C++
、JAVA
等语言都提供了类似数组的容器类,比如 C++
STL
中的 vector
。根据我的经验,一般情况下,推荐用容器开发,简单省事、代码易懂,底层和高性能开发用数组,毕竟容器的灵活性还是牺牲了一定性能的。
参考资料
《数据结构与算法之美》