首页 / 算法 / 数据结构与算法学习笔记之 从0编号的数组
数据结构与算法学习笔记之 从0编号的数组
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法学习笔记之 从0编号的数组,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2896字,纯文字阅读大概需要5分钟。
内容图文
![数据结构与算法学习笔记之 从0编号的数组](/upload/InfoBanner/zyjiaocheng/853/dc3322487a4c4f7f87d82453e90764c8.jpg)
前言
数组看似简单,但掌握精髓的却没有多少;他既是编程语言中的数据类型,又是最基础的数据结构;
一个小问题:
为什么数据要从0开始编号,而不是 从1开始呢?
正文
带着问题进入学习
如何实现随机访问?
什么是数组?
数组(array)是一种线性表数据结构,它用一组连续的内存空间来储存一组具有相同类型的数据。
我们从定义来分析:
线性表:
是数据排成像一条线一样的结构。每个线性表上的数据最多有前后两个方向。诸如数组,链表,队列,栈等都是线性表结构。
连续的内存空间和相同类型的数据:
这个特性是数组“随机访问”速度飞快的缘由,这也导致了从数组中删除、插入数据,为了保证连续性,需要大量的工作量
计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。
当计算机随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素的内存地址:
a[i]_address = base_address + i * data_type_size
data_type_siza表示数组中的每一个元素的大小。如果是int类型的数据,data_type_size为4个字节;
数组和链表的区别
链表适合插入、删除,时间复杂度为O(1),数组适合查找,但是这里要注意一下,时间复杂度并不是O(1),即便是排好序的数组,你用二分法查找,时间复杂度也是O(logn),
正确的描述为:数组支持随机访问,根据下标随机访问的时间复杂度为O(1)
低效的“插入”“删除”
插入操作
假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置,为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位,下面我们分析一下时间复杂度
如果在数组的末尾插入元素,那就不需要移动数据了,这时的时间复杂度为 O(1),但如果在数组的开头插入元素,那所有的数据都需要依次往后移动一位,所以最坏时间复杂度是 O(n),因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为 (1+2+…n)/n=O(n)
如果数组中的数据是有序的,我们在某个位置插入一个新的元素时,就必须按照刚才的方法搬移 k 之后的数据,如果数组中存储的数据并没有任何规律,数组只是被当作一个存储数据的集合。在这种情况下,如果要将某个数组插入到第 k 个位置
为了避免大规模的数据搬移,我们还有一个简单的办法就是
直接将第 k 位的数据搬移到数组元素的最后,把新的元素直接放入第 k 个位置。
删除操作
和插入类似,
如果删除数组末尾的数据,最好情况时间复杂度为 O(1);
如果删除开头的数据,则最坏情况时间复杂度为 O(n);
平均情况时间复杂度也为 O(n)
提高效率:
将多次删除操作中集中在一起执行,可以先记录已经删除的数据,但是不进行数据迁移,而仅仅是记录,当发现没有更多空间存储时,再执行真正的删除操作。这也是 JVM 标记清除垃圾回收算法的核心思想。
数组访问越界问题
C语言中的数据越界是一种未决行为,一般比较难发现的逻辑错误。相比之下,Java会有越界检查。
用数组还是容器?
数组先指定了空间大小,容器如ArrayList可以动态扩容。
1.希望存储基本类型数据,可以用数组
2.事先知道数据大小,并且操作简单,可以用数组
3.直观表示多维,可以用数组
4.业务开发,使用容器足够,开发框架,追求性能,首先数组。
为什么数组要从 0 开始编号?
由于数组是通过寻址公式,计算出该元素存储的内存地址:
a[i]_address = base_address + i * data_type_size
如果数组是从 1 开始计数,那么就会变成:
a[i]_address = base_address + (i-1)* data_type_size
以上内容为个人的学习笔记,仅作为学习交流之用。
内容总结
以上是互联网集市为您收集整理的数据结构与算法学习笔记之 从0编号的数组全部内容,希望文章能够帮你解决数据结构与算法学习笔记之 从0编号的数组所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。