集合

为什么数组索引从0开始呢？假如从1开始不行吗？

❒ 数组(Array)是一种用连续的内存空间存储相同数据类型数据的线性数据结构。

✔ 寻址公式:a[i]= baseAddress +i* dataTypeSize
✔ baseAddress:数组的首地址
✔ dataTypeSize:代表数组中元素类型的大小，int型的数据，dataTypeSize=4个字节

❒ 从1开始
✔ 寻址公式:a[i]= baseAddress + (i-1)* dataTypeSize
✔ 对于cpu来说，增加了一个减法指令

✔ 在根据数组索引获取元素的时候，会用索引和寻址公式来计算内存所对应的元素数据，寻址公式是:数组的首地址+索引乘以存储数据的类型大小
✔ 如果数组的索引从1开始，寻址公式中，就需要增加一次减法操作，对于CPU来说就多了一次指令，性能不高。

❒ 操作数组的时间复杂度(查找)
1.随机查询(根据索引查询)
数组元素的访问是通过下标来访问的，计算机通过数组的首地址和寻址公式能够很快速的找到想要访问的元素。
2.未知索引查询
情况一:查找数组内的元素，遍历查找55号数据 O(n)，二分查找:O(logn)

❒ 操作数组的时间复杂度(插入、删除)
✔ 数组是一段连续的内存空间，因此为了保证数组的连续性会使得数组的插入和删除的效率变的很低 O(n)。

1.数组(Array)是一种用连续的内存空间存储相同数据类型数据的线性数据结构。
2.数组下标为什么从0开始
✔ 寻址公式是:baseAddress + i * dataTypeSize，计算下标的内存地址效率较高
3.查找的时间复杂度
✔ 随机(通过下标)查询的时间复杂度是O(1)
✔ 查找元素(未知下标)的时间复杂度是O(n)
✔ 查找元素(未知下标但排序)通过二分查找的时间复杂度是O(logn)
4.插入和删除时间复杂度
✔ 插入和删除的时候，为了保证数组的内存连续性，需要挪动数组元素，平均时间复杂度为O(n)