1.1.4 数组的性能分析

数组是一种可随机访问的线性结构。由于数组存储于连续的地址空间，所以只要给定数组名（例如array）和数组的下标，就可以用O（1）时间复杂度直接定位到对应的元素。这也是数组作为顺序存储结构的优势所在。

数组的缺点主要体现在以下两方面。

（1）由于数组中的元素都是顺序存储的，且数组元素之间不能存在空隙，因此在插入、删除元素时会有大量元素移动，将严重影响效率。在数组中插入或删除一个元素的时间复杂度都是O（n）级的。

（2）没有扩容功能的数组的大小是固定的，在使用数组时容易出现越界问题。增加了自动扩容功能的数组虽然能避免内存越界问题，但在一定程度上又会导致内存资源的浪费（因为总会有一些空闲的数组空间）。

综上所述，数组比较适合读操作频繁，而插入、删除操作较少的场景。在定义数组时，应根据实际需求指定数组的大小。如果需要扩容，则应选择合适的扩容因子（扩容后数组容量是原容量的倍数），既要尽量提高空间的利用率、减少内存资源的浪费，又要最大限度地避免频繁扩容对数组性能的影响。