访问元素 - 实际上是 O(1) - Accessing Elements

据说 O(1( 操作的一个例子是访问数组中的元素。根据一个来源，O(1(可以通过以下方式定义：

[Big-O of 1] 表示算法的执行时间不依赖于输入的大小。它的执行时间是恒定的。

但是，如果要访问数组中的元素，操作的效率是否取决于数组中元素的数量？例如

int[] arr = new int[1000000];
addElements(arr, 1000000); //A function which adds 1 million arbitrary integers to the array. 
int foo = arr[55];

我不明白最后一条语句怎么能被描述为在 O(1( 中运行;数组中的 1,000,000 个元素对操作的运行时间没有影响吗？找到元素 55 肯定比找到元素 1 需要更长的时间吗？如果有的话，在我看来这看起来像 O(n(。

我确定我的推理是有缺陷的，但是，我只是想澄清一下如何说这在 O(1( 中运行？

数组

是一种数据结构，其中对象存储在连续的内存位置。所以原则上，如果你知道基对象的地址，你将能够找到ith对象的地址。

addr(a[i]) = addr(a[0]) + i*size(object)

这使得访问数组 O(1( 的ith元素。

编辑
从理论上讲，当我们谈论访问数组元素的复杂性时，我们谈论的是固定索引i。
输入大小 = O(n(
要访问ith元素，请addr(a[0]) + i*size(object) 。这个项与n无关，所以它被称为O(1(。

如何乘法仍然取决于i而不是n。它是常数 O(1(。

内存中元素的地址将是数组的基址加上数组中元素大小的索引乘以。因此，要访问该元素，您基本上只需访问memory_location + 55 * sizeof(int) 。

这当然假设您假设乘法需要恒定的时间，而不管输入的大小如何，如果您非常精确，这可以说是不正确的。

查找元素不是 O(1( - 但访问数组中的元素与查找元素无关 - 准确地说，您不与其他元素交互，除了单个元素之外，您不需要访问任何内容 - 您只需始终计算地址，无论数组有多大，这就是单个操作 - 因此 O(1(。

为语句生成的机器码(或者在 Java 的情况下，为虚拟机代码(

int foo = arr[55];

本质上是：

这三个指令在标准机器上都需要 O(1( 时间。

理论上，数组访问是 O(1(，正如其他人已经解释的那样，我想你的问题或多或少是一个理论问题。我仍然喜欢引入另一个方面。

实际上，如果阵列变大，阵列访问速度会变慢。原因有二：

如果我们说下标运算符(索引(具有 O(1( 时间复杂度，我们做出此语句不包括任何其他操作/语句/表达式/等的运行时。所以addElements不会影响操作。

找到元素 55 肯定比找到元素 1 需要更长的时间吗？

"找到"？哦不！"查找"意味着相对复杂的搜索操作。我们知道数组的基址。要确定 arr[55] 处的值，我们只需将 ¹ 55添加到基址并检索该内存位置的值。这绝对是 O(1(。

¹ 由于int数组的每个元素至少占用两个字节(使用 C 时(，因此这并不完全正确。 55需要先乘以int的大小。

数组

连续存储数据，不像链表或树或图形或其他数据结构使用引用来查找下一个/上一个元素。

您直观地知道第一个元素的访问时间为 O(1(。但是，您觉得^访问第 55 个元素的时间是 O(55(。这就是你做错的地方。你知道第一个元素的地址，所以它的访问时间是 O(1(。

但是您也知道^第 55 个元素的地址。它只是 1^st + size_of_each_element*54 的地址。

因此，您可以在 O(1( 时间内访问该元素以及数组的任何其他元素。这就是为什么你不能在一个数组中拥有多种类型的元素的原因，因为这会完全搞砸数学来找到数组第 n^个元素的地址。

因此，对数组中任何元素的访问都是 O(1(，并且所有元素必须是相同的类型。

访问元素 - 实际上是 O(1)