面试题库 › 客户端 › 数组按下标访问为什么是 O(1)

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

难度 ★☆☆在 1 场真实面经中被问到 方向:客户端考点:数据结构基础与选型

常见岗位:安卓

答案要点

  1. 数组内存连续且元素大小相同,第 i 个元素地址 = 首地址 + i × 元素大小
  2. 寻址只需固定次数的算术运算和一次内存访问,与数组长度无关,所以是 O(1) 随机访问
  3. 下标从 0 开始是因为下标表示相对首地址的偏移量,省去一次减法
  4. O(1) 只针对按下标访问;按值查找 O(n),有序时二分 O(log n),中间插入删除 O(n)
  5. 链表节点不连续,只能顺序遍历,按位置访问 O(n);数组连续存储对 CPU 缓存更友好

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题