为何数组元素引用被定义为constant time operation（常数时间操作）？

你的疑问核心是混淆了CPU硬件运算的特性和算法复杂度中“常数时间（O(1)）”的定义，下面逐一解释：

• 现代CPU的乘法运算耗时与数值大小无关
  你直觉上觉得乘大数字会更慢，但现代CPU的乘法器是硬件并行实现的，不管是计算16*1还是16*2789280，都是在固定的几个时钟周期内完成。比如x86架构的MUL或IMUL指令，执行周期数不会随操作数的数值大小变化——因为硬件是按二进制位并行处理，不是像手工计算那样逐位累加，所以大数值和小数值的乘法耗时完全一致。

• 数组地址计算是单条硬件指令级别的操作
  数组访问b[i]的地址计算，在汇编层面通常是用LEA（有效地址加载）指令直接完成：LEA 寄存器, [基地址 + 索引*元素大小]。这条指令的执行时间是固定的，不管索引是1还是几百万，都只需要一个时钟周期左右，不存在耗时差异。

• 测试中的“0秒”是精度问题，放大数值也不会改变耗时
  Colab显示耗时0秒，是因为这个计算的耗时远小于系统计时的最小精度（通常是毫秒级）。就算你设置更大的索引值，CPU执行这个乘法和地址计算的时间还是固定的几个周期，不会出现1秒和0.1秒的差异——因为运算的步骤数没有增加，只是数值本身变大，而硬件处理大数值的速度和小数值一样。

• 算法复杂度中“常数时间”的定义
  算法分析里的O(1)，指的是操作的执行时间不随输入规模（比如数组的大小）变化。不管数组有10个元素还是1000万个元素，访问任意位置的元素所需的步骤数是固定的，耗时不会随数组规模或索引数值的增大而线性增长。哪怕硬件上有极其微小的耗时差异（实际几乎不存在），这种差异也是固定的常数，不会影响复杂度的归类。

内容的提问来源于stack exchange，提问作者philen