为什么数组查询的复杂度为O(1)?

数组必须要内存中一块连续的空间,并且数组中必须存放相同的数据类型。

比如我们创建一个长度为10,数据类型为整型的数组,在内存中的地址是从1000开始,那么它在内存中的存储格式如下。

图片[1]-为什么数组查询的复杂度为O(1)?-编程社

由于每个整型数据占据 4 个字节的内存空间,因此整个数组的内存空间地址是 1000~1039,根据这个,我们就可以轻易算出数组中每个数据的内存下标地址。

利用这个特性,我们只要知道了数组下标,也就是数据在数组中的位置,比如下标 2,就可以计算得到这个数据在内存中的位置 1008,从而对这个位置的数据 241 进行快速读写访问,时间复杂度为 O(1)。

© 版权声明
THE END
喜欢就支持一下吧
点赞13赞赏 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容