定义
数组 (Array) 是一种线性表结构, 它用一组连续的内存空间来存储一组具有相同类型的数据.
在这个定义中有几个关键词:
线性表
所谓线性表就是数据会排成像一条线一样的结构. 也就是说线性表中数据元素之间的关系是一对一的关系, 即除了第一个和最后一个数据元素之外, 其它数据元素都是首尾相接的.
线性表包括: 顺序表和链表
顺序表里面元素的地址是连续的, 比如数组或者用数组实现的队列, 栈等
链表里面节点的地址不是连续的, 是通过指针连起来的. 如下图所示:
线性表具体解释可以参考线性表
而与线性表队里的概念就是费线性表, 比如二叉树, 堆, 图等等. 之所以叫非线性表是因为, 在非线性表中数据之间并不是一对一的前后关系, 如下所示:
连续内存空间 & 相同类型
正是基于这种定义的限制, 因此可以只需要计算出数组中某一元素相对于首地址 (base_address) 的偏移量, 就可以很方便的计算出这个元素的地址.
以一个长度为 4 的 int 类型的数组 int[] arr = new int[4]; 为例. 在初始化这个数组时, 计算机会给数组 arr 分配一块连续的内存空间 1000~1015, 其中首地址为 base_address = 1000, 如下图所示:
计算机会给每个内存单元分配一个物理地址, 然后计算机通过这些物理地址来访问内存中的数据. 当计算机需要访问数组中的某个元素是, 就可以通过下面的寻址公式, 计算出该元素的内存地址:
arr[i]_address = base_address + i * data_type_size
其中 i 代表需要访问的元素下标, base_address 代表首地址, data_type_size_代表每个元素占用的内存大小, 比如数组中存储的是 java 的 int 类型, 所以 data_type_size_也就是 4 个字节.
数组的基本操作
插入操作
删除操作
查找操作
插入操作
插入操作有两种情况.
在数组的末尾插入元素
如果是在末尾插入操作, 不需要移动任何元素的位置, 直接在数组最后位置添加上一个新的元素即可. 因此在数组末尾插入数据的时间复杂度为 O(1)
在数组头部插入元素.
如果是在开头位置插入元素, 那为了保持内存数据的连续性, 所有的数据都需要依次往后移动一位, 所以最坏时间复杂度为 O(n)
删除操作
和插入元素类似, 如果要删除数组中第 K 位置的数据, 为了保持内存的连续性, 需要将 K + 1 到最后一个元素的位置都向前移动一位. 同样也分两种情况
删除数组末尾元素
最好时间复杂度为 O(1)
删除数组头部元素
最坏时间复杂度为 O(n)
随机访问
当我们已经知道某元素在数组中的下标时, 我们就可以直接通过下标来访问此元素, 比如假设我们已经知道数字 23 在数组 [10, 15, 23, 45] 的下标是 2, 所以我们可以直接通过 arr[2]来指向 23. 因此数组随机访问的时间复杂度是 O(1)
查找操作
假设我们需要在数组 [10, 15, 23, 45] 中查找是否有 23 时, 因为我们不知道元素 23 所处的下标是多少, 因此需要从头到尾依次遍历数组中的每一个元素, 并判断是否等于 23. 代码可以如下:
- for (let index = 0; index < array.length; index++) {
- if(element === array[index]) {
- return index;
- }
- }
- 1
- 2
- 3
- 4
- 5
因此数组中查找某元素的时间复杂度为 O(n)
数组时间复杂度总结
附录
Android 高级技术大纲, 以及系统进阶视频;
Android 高级技术大纲
Android 高级进阶视频资料
获取方式;
加 Android 进阶群; 701740775. 即可前往免费领取. 免费备注一下简书领取进阶资料
来源: http://www.jianshu.com/p/44b2d30e5be2