首页 / 算法 / 数据结构与算法之美笔记——数组
数据结构与算法之美笔记——数组
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法之美笔记——数组,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2814字,纯文字阅读大概需要5分钟。
内容图文
![数据结构与算法之美笔记——数组](/upload/InfoBanner/zyjiaocheng/835/711a1b56e3f247cfa5a00cee888a4067.jpg)
摘要:
数组是最简单基本的数据结构,属于一种线性表数据结构,它有着可以快速随机访问元素的优势,但也有低效的删除和插入操作,容器对数组的封装会简化对数组的操作,也会对带来一些劣势。
特性原理
数组可以说是日常工作学习中最常见到的数据结构,但也因为常见往往忽视了其重要性,包括数组这种数据结构适合的使用场景,它的优势也劣势等,要了解这些需要从数组的原理说起。
数组是其实是一组连续的内存空间,用来存储一组相同类型的数据,它是一种线性表数据结构。那什么是线性表,线性表就是数据排成一条线一样的结构,每个数据最多只有前后两个方向,像链表、栈、队列等都是线性表数据结构。
数组的另一个特点就是连续内存空间存储,并且都是存储的同类型数据。因为这个特点,数组中每个元素的地址都可以使用基础地址与下标通过寻址公式快速计算出来。
a[i]_address=base_address + i * data_type_size
base_address就是这块连续内存的首地址
data_type_size就是元素的大小,例如元素是int类型时,data_type_size大小就为4
所以数组的随机访问只需通过一个公式就可以完成,时间复杂度也就是O(1)。
插入与删除操作
因为数组需要满足连续内存空间存储要求,导致删除或者插入操作会变得低效。如果插入元素到数组末尾时,直接插入就可以,但当插入元素是在数组头时需要将元素搬移,再将数据插入数组插入首位,所以数组的插入操作的最好时间复杂度和最坏时间复杂度分别是O(1)和O(n)。
当插入元素时,插入元素的位置有n种可能,每种可能下数组元素需要搬移的操作次数分别为n,n-1,n-2,...,3,2,1
次,平均时间复杂度为
1/n + 2/n + 3/n + ... + n/n=n(n+1)/2/n=(n+1)/2=O(n)
但是插入操作在特定情况下时间复杂度降为O(1)。当数组不要求元素有序时,插入操作就可以将要插入位置的元素搬移到数组元素的最后,再把元素插入相应位置,时间复杂度就为O(1)。
删除操作与插入操作相似,最好时间复杂度为O(1),最坏时间复杂度为O(n),平均时间复杂度为O(n)。但删除操作在某些场景下,不是非要追求数组中元素连续性时,可以先把数据标记为删除,当数组没有存储空间时再统一一次删除被标记的数据,这样可以把多次数据搬移操作整合为一次。
对比容器类
容器类是对数组的封装,用Java中的ArrayList举例,它将数组的插入、删除操作细节封装了起来,并且支持动态扩容,数组存储空间不够时需要创建一个更大空间的数组,再将旧数组中的元素搬移到新数组中。虽然容器支持动态扩容,但扩容操作比较消耗资源,使用容器类时如果能够估算大概的数据容量在初始化容器类时可以初始化空间的大小,避免在扩容过程中进行的资源消耗。
虽然ArrayList有简化数组操作和动态扩容储多优势,但ArrayList不能存储基本类型,需要使用包装类型,在使用时就会增加自动装箱和自动拆箱操作,肯定会增加一些性能消耗,同时对多维数组的表示不是很直观,ArrayList表示二维数组Object[][] array
需要写为ArrayList<ArrayList> array
。
虽然很多语言对数组提供了容器类,但数组也有自己的适用场景,比较关注性能时,表示多维数组时都可以考虑直接使用数组。
课后题目
分析一下二维数组的寻址公式。
假设大小为m * n
大小的二维数组a[i][j],i<n,j<m,寻址公式为
a[i][j]_address = base_address + (i * n + j) * data_type_size
文章中如有问题欢迎留言指正
数据结构与算法之美笔记系列将会做为我对王争老师此专栏的学习笔记,如想了解更多王争老师专栏的详情请到极客时间自行搜索。
内容总结
以上是互联网集市为您收集整理的数据结构与算法之美笔记——数组全部内容,希望文章能够帮你解决数据结构与算法之美笔记——数组所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。