为什么在恒定时间(O(1))中访问数组中的任何单个元素？

Question

根据Wikipedia,访问数组中的任何单个元素需要恒定的时间,因为只需要执行一个操作来定位它.

对我来说,幕后发生的事情可能看起来像这样:

a)线性搜索(例如,我想访问元素5.我在索引0开始搜索,如果它不等于5,我去索引1等)这是O(n) - 其中n是数组的长度

b)如果数组存储为B树,这将给出O(log n)

我认为没有其他方法.

有人可以在O(1)中解释为什么以及如何做到这一点？

Answer 1

数组从特定的内存地址开始start.每个元素占用相同的字节数element_size.数组元素从起始地址开始一个接一个地位于存储器中.所以,你可以计算出该元素的内存地址i用start + i * element_size.该计算与阵列大小无关,因此O(1).

Answer 2

理论上,数组的元素具有相同的已知大小,并且它们位于内存的连续部分中,因此如果A要访问任何元素,如果数组的开头位于内存地址,则必须按如下方式计算其地址:

A + item_size*index 所以这是一个恒定的时间操作.

Answer 3

访问单个元素不是找到值为 的元素x。

访问一个元素i意味着在数组的第 i 个位置获取元素。

这样做是O(1)因为它非常简单（恒定数量的数学计算），其中元素位于给定索引、数组的开头和每个元素的大小。

RAM 内存提供了一个恒定时间（或者更准确地说，一个有界时间）来访问 RAM 中的每个地址，并且由于找到地址是 O(1)，并且检索其中的元素也是 O(1)，它给你总共O(1).

查找其值为 的元素x是否确实有Omega(n)问题，除非数组中有更多信息（例如已排序）。