数组按下标访问为什么是 O(1)
答案要点
- 数组内存连续且元素大小相同,第 i 个元素地址 = 首地址 + i × 元素大小
- 寻址只需固定次数的算术运算和一次内存访问,与数组长度无关,所以是 O(1) 随机访问
- 下标从 0 开始是因为下标表示相对首地址的偏移量,省去一次减法
- O(1) 只针对按下标访问;按值查找 O(n),有序时二分 O(log n),中间插入删除 O(n)
- 链表节点不连续,只能顺序遍历,按位置访问 O(n);数组连续存储对 CPU 缓存更友好
易错点
- 把按值查找也说成 O(1)
- 只说“因为有下标”,不解释连续内存和地址计算
- 误以为数组插入删除也是 O(1)
- 忽视缓存命中对实际性能的影响,只比较理论复杂度
面试官常见追问
- 二维数组的元素地址怎么算?
- 既然数组随机访问快,为什么还需要链表?
- 动态数组如 ArrayList 的 add 复杂度是多少?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。