据说，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];
数组是一种数据结构，其中对象存储在连续的内存位置上。因此，原则上，如果您知道基本对象的地址，您就能够找到第 i 个对象的地址。
addr(a[i]) = addr(a[0]) + i*size(object)
这使得访问数组的第 i 个元素的时间复杂度为 O(1)。
编辑
从理论上讲，当我们讨论访问数组元素的复杂度时，我们是针对固定的索引 i 进行讨论的。
输入大小为 O(n)
要访问第 i 个元素，则为 addr(a[0]) + i*size(object)。该项与 n 无关，因此它被称为 O(1)。
然而，乘法仍然取决于 i，但不取决于 n。它的时间复杂度是常数级的 O(1)。
一个元素在内存中的地址将是数组的基地址加上元素在数组中的下标乘以元素大小。因此，要访问该元素，您只需访问 memory_location + 55 * sizeof(int)。
当然，这假设乘法需要恒定时间，而不考虑输入的大小，如果您非常精确，则可以认为这是不正确的。
ith个索引”的上下文中。 - C.B.要查找一个元素并不是O(1)——但访问数组中的元素与查找元素无关——确切地说，您不与其他元素进行交互，您不需要访问除单个元素之外的任何内容——您只需始终计算地址，无论数组有多大，这就是单个操作——因此是O(1)。
对于语句生成的机器码（或者在Java中生成的虚拟机器码）
int foo = arr[55];
本质上是：
这三条指令在标准计算机上都只需要 O(1) 的时间。
理论上，如其他人已经解释的那样，数组访问是O(1)的。我猜你的问题或多或少是一个理论性的问题。但我还是想带入另一个方面。
实际上，如果数组变得很大，数组访问会变慢。原因有两个：
addElements不会影响操作。arr[55]处的值，我们只需将551加到基地址上，并检索该内存位置处的值。这绝对是O(1)。
1 由于在使用C语言时，int数组的每个元素至少占用两个字节，因此这并不完全正确。需要先将55乘以int的大小。
数组将数据连续存储，不同于使用引用查找下一个/上一个元素的链表、树或图表等其他数据结构。
对于第一个元素的访问时间为O(1)是直观的。然而，你可能认为第55个元素的访问时间是O(55)，这就是你犯错的地方。你知道第一个元素的地址，所以它的访问时间是O(1)。
但是，你也知道第55个元素的地址。它只是1号元素的地址+每个元素的大小*54。
因此，你可以以O(1)的时间访问数组的任何元素，这也是为什么你不能在数组中拥有多种类型的元素，因为那会完全搞乱查找数组第n个元素的地址的数学运算。
因此，对于数组中的任何元素，访问都是O(1)，所有元素必须是相同类型的。
i。 - njlarsson