数组的三种操作时间复杂度

按下标随机查找时间复杂度：O(1) 插入时间复杂度：O(n) 删除时间复杂度：O(n)

查找操作

因为数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。所以，我们在通过下标i查找某个元素的时候，通过计算a[i]_address = base_address + i * data_type_size就可以查到该元素的偏移地址了。因为只需要经过有限次的计算，因此查找操作的时间复杂度为O(1)。

插入操作

因为数组的元素在内存区域中是连续的，所以每次插入操作都会使后面的元素整体往后迁移。 因此，若数组中的元素顺序不可变，那么时间复杂度为O(n)。若数组中的元素顺序可变，也就是说该数组只是用来存储元素数据的数据结构，那么我们可以把插入位置的元素用有限的操作迁移到地址最末端。因此时间复杂度也可以为O(1)。

删除操作

删除操作的时间复杂度与插入操作非常类似。 不过若数组的顺序不可变，删除操作可以集中进行，我们可以在删除元素后不着急迁移数据，而是记录该元素的位置，在没有更多空间存储数据时，进行一次集中的迁移。

数组越界

在c语言中，数组是可以越界访问的，所以一定要注意数组的越界问题。

数组为什么从0而非1开始计数？

现实原因：数组进行的最多的是查找操作，从0计数时的查找操作公式为a[k]_address = base_address + k * type_size，而从1计数时的查找操作公式为a[k]_address = base_address + (k-1)*type_size。可以看到，数组的每次查找都需要一次减法操作，因为数组查找在程序中是非常常用的，所以为了使底层性能达到极致就采用从0开始计数的方式。 历史原因：因为C语言设计者用0开始计数数组下标，虽然其它语言无需像C语言一样将性能做到极致，可以适当的为了易用性而损失性能，不过为了减少学习成本就继续沿用了这一习惯。