微信公众号:BoomDev
如有问题或建议请留言
最近更新:2018-10-02
读《数据结构与算法》笔记-数组为什么从 0 开始编号
数组(Array) 是一种线性表数据结构,用一组连续的内存空间来存储一组具有相同类型的数据
线性结构
- 线性表(Linear List):数据排成一条线一样的结构,每个线性表上的数据最多只有前后两个方向。数组、链表、队列、栈也是线性表结构。
- 非线性表:二叉树、堆、图。
随机访问
- 连续的内存空间和相同类型的数据,正是这两个限制,它才有了随机访问的特性。这两个限制也让数组的删除、插入变得非常低效,为了保证连续性,就需要做大量的数据搬迁工作
数组内存地址分配
数组如何实现根据下标随机访问数组元素的?
计算机通过地址来访问内存中的数据,当需要随机访问数组中的某个元素时,会首先通过寻址公式计算出该元素存储的内存地址:
|
|
|
|
为什么从 0 开始编号
- 随机访问内存寻址
下标
最确切的定义应该是偏移(offset)
,如果用 a 来表示数组的首地址,a[0] 就是偏移为 0 的位置既首地址,a[k] 就是表示偏移为 k 个 type_size 的位置,所以计算 a[k] 的内存地址公式:
|
|
如果数组从 1 开始计数,计算 a[k] 的内存地址是:
|
|
这样每次随机访问数组元素都多了一次运算,对 CPU 来说,就是多了一次减法指令。
- 最主要的原因是历史原因。
小结:
- 使用 ArrayList 不需要关系底层容器逻辑,每次存储空间不够的时候,它都会扩容 1.5 倍的大小。扩容操作涉及内存申请和数据迁移,这个操作是比较耗时的,如果能先确定存储数据的大小,最好在创建 ArrayList 的时候先指定数据大小
纠错
- 错误认识:数组的查找操作时间复杂度并不是 O(1),即便是排好的数组,用二分法查找,时间复杂度也是 O(logn)
- 正确表述:数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。
我是一名有备而来的 Android 工程师
微信公众号:BoomDev
欢迎关注我、一起学习、一起进步!