arrays - 访问元素——真的是 O(1) 吗？

Question

它is said O(1) 操作的一个示例是访问数组中的元素。根据一个source , O(1) 可以定义如下:

[Big-O of 1] means that the execution time of the algorithm does not depend on the size of the input. Its execution time is constant.

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

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) 中运行？

Answer 1

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

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

这使得访问数组 O(1) 的 第 元素成为可能。

编辑
理论上，当我们谈论访问数组元素的复杂性时，我们谈论的是固定索引 i。
输入大小 = O(n)
要访问 ith<​​ 元素，addr(a[0]) + i*size(object)。此项独立于 n，因此称为 O(1)。

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