为何数组访问被认定为常数时间？地址计算相关疑问

首先得明确**常数时间（O(1)）**的核心定义：操作的执行耗时不随输入规模变化，不管你访问的是第1个还是第100万个元素，完成这个操作的时间是固定的，和元素位置的n值大小无关。

你提到的地址计算adr + n*a[size]，其实并没有“n越大步骤越多”的问题：

• 数组元素的大小（比如int占4字节、double占8字节）是编译期就确定的固定值，不是运行时才计算的变量。
• 现代CPU的乘法指令是固定周期完成的——不管n是1还是1000000，n * 元素大小这个乘法操作都只需要一条CPU指令，耗时完全一样，不会因为n的数值变大而增加运算步骤。
• 后续的地址加法adr + 乘积也是单周期的CPU指令，同样和n的大小无关。

换句话说，不管n是多少，数组元素的地址计算都只需要“乘法+加法”这两个固定的CPU操作，再加上一次内存访问，整个过程的耗时是恒定的，不会随着n的增长而变长，所以我们说数组的随机访问是常数时间操作。

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