数据结构-数组

发布于:2024-07-11 ⋅ 阅读:(17) ⋅ 点赞:(0)

1.什么是数组?

数组是一组用连续内存空间存储相同数据类型数据的线性数据结构

数组一般下标从0开始到n-1;

2.数组寻址公式

a[i]=baseAddress+i*dataTypeSize 这里baseAddress代表数组的首地址,i是索引,dataTypeSize 是数据的数据类型所占内存多少字节;比如,int 和float占4字节,long和double占8字节,char占2字节,byte占1字节,short占2字节。当一个数据是int类型,那么dataTypeSize=4.

例:假设一个数组有22,33,44....,这些元素都是int类型,并且内存地址是从10开始的,那么33是从多少内存地址开始的?

答:可以知baseAddress=10,由于数组索引是从0开始,那么i=1,int占4字节,所以dataTypeSize =4;那么33的的开始内存地址可以得到a[1]=10+1*4=14。

2.1反思:为什么数组索引要从0开始,而不从1开始呢?

还是上面那个题来解答,但是呢刚开始的寻址公式就不行了,就要改成a[i]=baseAddress+(i-1)*dataTypeSize

可以看见,这里多了个减法指令操作,那么对于cpu就要多一次操作,而当进行大量甚至上亿的寻址操作时,这个减法操作会给cpu带来更大的压力,降低cpu的性能,因此用0不用1就相当于0的寻址公式在1的寻址公式上做了优化,会更加高效。

3.操作数组的时间复杂度

3.1 查找操作

3.1. 1 随机查询(根据索引查询)

数组元素的访问通过索引的方式,那么计算机就能通过首地址和寻址公式快速找到目标元素,那么此时的时间复杂度为O(1)。

3.1.2 未知查询

3.1.2.1 在不知道目标元素索引,此时我们就需要从下标0开始遍历数组,如果第一次遍历就得到了目标元素,时间复杂度是O(1);数组再不排序的情况下,直接遍历去找元素,那么平均的时间复杂度是O(n)

3.1.2.2 在已经排过序的数组内找元素,如果依旧是从0索引开始找,依旧是O(n);在排过序的情况下,可以用二分查找法,时间复杂度是O(logn)

3.2 插入删除操作

由于数组是一组连续的内存空间,因此为了保证数组的连续性会使数组的插入删除操作效率变很低。

3.2.1 一般情况

由于进行插入删除操作,都会伴随着将插入或删除位置后面的元素进行整体往后挪或往前挪,那么时间复杂度为O(n)。

3.2.2 特殊情况

假如是删除数组最后一个位置的元素或者在最后一个元素的后面添加元素,那么此时的时间复杂度是O(1)。