赞
踩
特性:数据码成一排进行存放,每一个数据对应一个索引,支持随机访问,初始化必须指定大小
使用:Java中初始化:int[] arr = new int[10] 或 int[] arr = new int[]{ 1,2,3 }
其他:数组索引可以有意义也可没有意义,但最好应用于索引有意义的情况因为其支持随机访问的特性,根据索引查找对应数据所用的时间复杂度为O(1)
具体实现代码https://github.com/GuZhC/dataStructureCoding
由于很多时候我们开始的时候不知道需要创建多大长度的数组,此时可以在创建的时候创建一个很大的静态数据,但这样做会耗费不必要的存储空间,也并不能绝对保证元素个数不超过数组容量。此时动态数组的出现就解决了这个问题
动态数组底层使用的是静态数组实现的大概实现思路如下:
首先创建一个固定容量的静态数组,在执行插入元素是超过当前数组预定义的最大值时,重新创建一个更大容量的数组,将小容量数组数据拷贝到新数组中,接下来的插入操作就使用我们新创建的这个数组。删除元素也同理,删除元素后当前元素总数小于数组容量的一半(实际并不是一半举例而已)时重新创建一个小容量数组,将旧数组内容拷贝过来,之后就使用新创建的这个数组,这么做既不会浪费太多空间也能保证了可以存储足够多的数组。
在Java中的ArrayList就是一个动态数组,的实现方式大概是相同的,扩容过程需要调用底层System.arraycopy()方法进行大量的数组复制操作;在删除元素时并不会减少数组的容量(如果需要缩小数组容量,可以调用trimToSize()方法);在查找元素时要遍历数组,对于非null的元素采取equals的方式寻找。
什么是时间复杂度:
常见的时间复杂度有:O(1),O(n),O(lgn),O(nlogn),O(n^2)
大O描述的是算法的运行时间和输入数据之间的关系
例:
- public static int sun(int[] nums){
- int sun = 0;
- for(int num:nums) sum +=num;
- return sum;
- }
上面是对数组nums求和的过程,n此时代表的是nums的中的元素个数,在这个函数中运行的时间是和这个n是成线性关系的,线性方程是:T= c1*n+c2 (c1可以看做是sum+=num所花的时间,c2可看做sun初始化,以及最后return所花的时间),这里看的是当n趋近于无穷的时候,所以忽略常数直接用大O(n)表示,所以这个函数的时间复杂度是O(n),其他同理。
值得注意的是O(n)复杂度并不代表这个算法就比O(n^2)快,例如:T= 10000*n+10000 ,T= 1*n*n+0 这个例子中当n为10可以看到O(n)反而快,但n=10000的时候O(n^2)就远远慢于O(n)了,所以时间复杂度又叫做渐进时间复杂度,描述的是n趋于无穷的情况。
均摊时间复杂度,复杂度震荡,后面再说
动态数组时间复杂度分析:
添加元素:O(n)
向索引为index的地方添加元素,那么index之后的元素都需要像后移动,所以向数组头添加元素需要进行n次操作即O(n),向末尾只需进行一次操作即O(1),通过概率论知识计算出每次添平均需要进行n/2次操作,所以时间复杂度为O(n/2)省略常数1/2,添加操作的时间复杂度就为O(n)。
但是有的胸弟就发现了向末尾添加元素不一定时间复杂度为O(1)啊,因为可能进行扩容,此时就用到了上面没说的均摊时间复杂度,扩容这个操作不是每次都触发的,例如容量为10,一直添加元素在第10次的时候才触发了扩容,此时添加10个元素进行了20次操作, 均摊给每一次操作时间复杂度为O(2),O(2)就等于O(1),这就叫做均摊时间复杂度。
此时又有胸弟找茬了,如果在元素占满数组容量时进行扩容到原来容量的2倍,在元素个数小于数组容量一半时进行缩容为当前容量一半,那么如果总是在动态数组末尾添加一个元素,再删除一个元素,重复这两个步骤,不断的进行扩容和缩容,此时时间复杂度就为O(n)了,这就叫做复杂度震荡,但这个问题是可以解决的,只需要在元素个数小于容量的1/4时候才进行缩容为当前容量的一半。一个好的算法应该尽量避免复杂度震荡。
删除元素:O(n) 同添加相同思路
查询元素:O(1) 每次只需根据索引进行一次操作
总结:由于ArrayList对元素的增加和删除都会引起数组的内存分配空间动态发生变化。因此,对其进行插入和删除速度较慢,但检索速度是很快的。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。