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

Question

它说的是一个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)中运行？

Answer 1

数组是一种数据结构,其中对象存储在连续的内存位置.因此原则上,如果您知道基础对象的地址,您将能够找到ith对象的地址.

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

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

编辑
理论上,当我们谈论访问数组元素的复杂性时,我们谈论固定索引i.
输入大小= O(n)
访问ith元素,addr(a[0]) + i*size(object).这个术语是独立的n,所以据说是O(1).

乘法如何仍取决于i但不取决于n.它是常数O(1).

Answer 2

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

当然，这假设您假设无论输入的大小如何，乘法都需要恒定的时间，如果您非常精确，这可能是不正确的