数组的随机访问【简介】

学习笔记 马富天 2020-07-09 16:54:39 8 0

【摘要】假如有人问你数组和链表的区别,也许你会回答:"链表适合插入、删除操作,插入、删除的时间复杂度为 O(1);数组适合查找,查找的时间复杂度为 O(1)"。然而实际上,这种表述是不准确的。数组确实是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,用二分法查找,时间复杂度也是 O(logn)。正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。这是为什么呢,那么我们就进入本文的主讲核心内容:数组的随机访问,来一起了解。

(一)什么是数组?

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

关键点:线性表、连续的内存空间,相同类型的数据

问:啥是线性表?

答:线性表(Linear List),顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构。

问:连续的内存空间指的是什么?

答:计算机在分配内存空间的时候都会对应分配一个内存地址,连续的内存空间对应的是指连续的内存地址,计算机是通过访问内存地址会获取内存中的值。

问:为什么要是相同数据类型?

答:数据类型相同那么数据存储所占用内存大小一样。

正是因为这两个限制,它才有了一个堪称 "杀手锏" 的特性:"随机访问"。但有利就有弊,这两个限制也让数组的很多操作变得非常低效,比如要想在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。

(二)说到数据的访问,那你知道数组是如何实现根据下标随机访问数组元素的吗?

举个例子:一个长度为 10 的 int 类型数组 int[] a = new int[10],计算机给数组 a 分配了一块连续内存空间 1000 ~ 1039。(这里 int 类型为 4 个字节),其中,内存块的首地址为 base_address = 1000.

当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:

  1. a[i]_address = base_address + i * data_type_size

如 i = 2(第三个元素):

  1. a2_address = base_address + 2 * data_type_size = 1000 + 2 * 4 = 1008

其中 data_type_size 为数组中每个元素的大小

因为数组是连续存储的,所以根据首地址和下标,通过寻址公式就能直接计算出对应的内存地址,找出数据。

(三)为什么数组的下标都是从 0 开始?

若下标为 1 开始:获取第 3 个元素的值,1000 +(3-1)* 4(数据类型占用的内存)= 1008,计算得出第三个元素的内存地址的位置;

若下标从 0 开始:获取第 3 个元素的值,1000 + 2 * 4(数据类型占用的内存)= 1008,省去了一个减法的动作,提高了访问的效率。

今后如果再有人问起链表和数组的区别,那么一定要记得这样回答:数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

版权归 马富天PHP博客 所有

本文标题:《数组的随机访问【简介】》

本文链接地址:http://www.numberer.net/450.html

转载请务必注明出处,小生将不胜感激,谢谢! 喜欢本文或觉得本文对您有帮助,请分享给您的朋友 ^_^

0

0

上一篇《 MySQL 中的 update join on 使用方法 》 下一篇《 Neo4j - CQL 查询语句的简介【纯个人总结】 》

暂无评论

评论审核未开启
表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情
验证码

TOP10

  • 浏览最多
  • 评论最多