数组

数组是什么？

• 定义: 一串相同类型元素在连续内存中的顺序存储;
• 逻辑结构: 线性结构;
• 物理结构: 连续空间存储;

数组的下标访问为什么是 O(1)？

• 定位公式: 元素地址 = 首地址 + 下标 × 元素大小;
• 结果: 一次乘法加一次加法即可定位, 与元素数量无关;

数组有哪些优点和缺点？

	说明
优点	通过内存地址直接访问元素, 时间复杂度 O(1)
缺点一	初始化后长度不可变: 超出范围的元素会丢失, 预留过长则内存浪费
缺点二	插入与删除需要搬移后续元素, 时间复杂度 O(n)

插入与删除的代价来自哪里？

• 在位置 i 插入: 下标 [i, n-1] 的元素整体后移一位;
• 删除位置 i: 下标 [i+1, n-1] 的元素整体前移一位;
• 在末尾插入或删除不需要搬移, 为 O(1);