为什么在恒定时间（o（1））中访问数组中的任何单个元素？ wikipedia的符号，访问数组中的任何单个元素需要恒定的时间，因为只需执行一个操作即可找到它。 对我来说，幕后发生的事情可能看起来很

Question

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

a）搜索是线性完成的（例如，我想访问元素5。我以索引0开始搜索，如果它不等于5，我转到索引1等。） 这是o（n） - 其中n是阵列的长度 B）如果阵列存储为b-tree，则会给出O（log n）

我看不到其他方法。

有人可以解释为什么以及如何在o（1）中完成此操作？

一个数组从特定的内存地址开始。每个元素都占据相同数量的字节

start

。数组元素是从开始地址打开的内存中的一个接一个位置。因此，您可以用

element_size

计算元素的内存地址。该计算独立于阵列大小，因此是

i

Answer 1

数组的理论元素具有相同的已知大小，它们位于内存的连续部分，因此，如果数组的开始位于

start + i * element_size

内存地址，如果要访问任何元素，则必须计算其地址这样：

O(1)

因此，这是一个恒定的时间操作。
    

单个元素未找到一个值为

A

的元素。 accessing一个元素

Answer 2

意味着将元素在数组的“位置”位置下获取。

这是在

x

中完成的，因为它非常简单（数学计算的恒定数量），其中元素位于给定索引，数组的开始和每个元素的大小。

RAM内存提供了一个恒定的时间（或更确切的时间，有限的时间）来访问RAM中的每个地址，并且由于找到地址为O（1），并且在其中检索元素也是O（1），O（1），它为您提供了总共

i

。

查找值为

O(1)

Answer 3

通常将数组组织为记忆的连续块，其中可以通过索引计算访问每个位置。该索引计算不能在任意大小的阵列中恒定时间进行，但是出于可寻址空间的原因，所涉及的数字是由机器单词大小界定的，因此恒定时间的假设是合理的。
    

如果您有int的数组。每个int在Java中为32位。如果您有Java中的10个整数，则意味着您分配320位的内存。然后计算机知道

0-索引在内存中-39200

last索引在内存39200 +您的数组的总内存= 39200 + 320 =39520

，然后如果要访问索引3。那么它是39200 + 32*3 =39296.

这一切都取决于您的对象在数组中存储的内存多少。只要记住数组占据整个内存。

lastElement的索引将为39200 + 9 * 32 + 1 = 39 489。通常，如果要访问ton`thth元素值，计算机将读取size_of_type_of_of_array位，从array_offset_in_in_memory +（n -1） * size_of_type_of_of_array + 1。 - 尼克·洛伊 2019年8月17日评论13：44