阵列访问复杂性

Question

在Java中,我需要array1[index]在代码中多次访问.

即使对于超大型阵列,我还能假设每个单一阵列访问需要恒定时间吗？
这在语言或底层架构之间有区别吗？

Answer 1

数组查找始终 是O(1).它不依赖于数组的大小.关于数组的基本思想是它包含具有固定大小的对象/引用,因此您可以只size * index拥有要查找的对象的位置.

因此,它不像是一个LinkedList(这是O(n)也没有HashMap被O(1)摊销.

我认为大多数语言都是如此.一个例外可能是javascript,因此请确保检查您正在使用的语言的文档.

Answer 2

对于array1大小的大值,我可以假设每个单个数组访问(array1 [index])需要恒定的时间吗？

在Java中,是的.同样在C,C++和C#中,禁止OS级别的内存分页问题,​​这些问题可能超出了范围.

此访问时间是否取决于语言(java与C++)或底层架构？

如果所讨论的语言在通常的"连续内存块"意义上调用"数组"并不是真正的数组,那么它就可以.(JavaScript做到了;它的Array([])类型实际上是一个映射 ; PHP使用术语"数组"作为"关联数组"的简写[例如,map].)因此对于给定的环境/语言,值得检查术语是否为被滥用或松散使用.

Answer 3

访问数组中的元素是常数时间（它只是计算地址偏移量）。此行为对于您列出的所有语言都是一致的。虽然不应该假设它适用于所有语言，但它适用于大多数语言。

在缓存未命中/命中、管道等方面存在一些复杂性，但基本上是恒定时间。

但对于 List 而言，情况并非如此。一些 List 实现为不同的操作提供不同的性能特征。

扩展复杂性：

问题是“大数组的访问速度会变慢吗”。正确答案是“是”。

就访问顺序而言，它将保持 O(1)，但实际访问可能需要更长的时间。例如，如果数组的大小导致缓存未命中（因此数据需要从主内存获取到处理器的缓存）和/或内存分页问题（因此数据需要从磁盘获取），它会变得更慢，尽管那样是任何大型数据集的属性，而不是数组的属性。

在大多数情况下，这种差异并不值得担心。在您开始担心缓存未命中之类的事情之前，我们正在谈论相当重的优化。但是，正如这个问题所说明的那样，值得了解这些事情：

为什么处理排序数组比处理未排序数组更快？

由于处理器工作方式的细节，代码上看似无关的细节（数组的预排序）从表面上看应该总是以相同的时间运行五倍。