arrays - 为什么访问数组中的任何单个元素都是在恒定时间 ( O(1) ) 内完成的？

Question

根据 Wikipedia ，访问数组中的任何单个元素都需要常数时间，因为只需执行一个操作即可定位它。

对我来说，幕后发生的事情可能是这样的:

a) 搜索是线性完成的(例如，我想访问元素 5。我从索引 0 开始搜索，如果它不等于 5，我就转到索引 1 等)这是 O(n) —— 其中 n 是数组的长度

b) 如果数组存储为 B 树，则复杂度为 O(log n)

我看不到其他方法。

有人可以解释为什么以及如何在 O(1) 中完成吗？

Answer 1

数组从特定的内存地址开始start。每个元素占用相同数量的字节 element_size。数组元素在内存中从起始地址开始依次定位。所以你可以用start + i * element_size计算元素i的内存地址。此计算与数组大小无关，因此为 O(1)。