arrays访问复杂性
在Java中，我需要在代码中多次访问array1[index] 。
即使对于超大型arrays，我是否可以假设每个单一arrays访问需要恒定时间？
这在语言或底层架构之间有区别吗？
对于array1大小为N的大值，我可以假设每个单独的数组访问（array1 [index]）需要恒定的时间吗？
在Java中，是的。 同样在C，C ++和C＃中，禁止OS级别的内存分页问题，这些问题可能超出了范围。
此访问时间是否取决于语言（java与C ++）或底层架构？
如果所讨论的语言在通常的“连续内存块”意义上调用不是真正数组的“数组”，它就可以。 （JavaScript做到了;它的Array （ [] ）类型实际上是一个映射 ; PHP使用术语“数组”作为“关联数组”的简写[例如，map]。）因此对于给定的环境/语言，值得检查一下该术语未被滥用或松散使用。
数组查找始终为 O(1) 。 它不依赖于数组的大小。 关于数组的基本思想是它包含具有固定大小的对象/引用，因此你可以只使用size * index来获得你正在寻找的对象的位置。
所以它不像LinkedList （它是O(n)也不是O(1)摊销的HashMap 。
我认为大多数语言都是如此。 一个例外可能是javascript，因此请务必查看您正在使用的语言的文档。
访问数组中的元素是恒定时间（它只计算地址偏移量）。 对于您列出的所有语言，此行为都是一致的。 虽然不应该假定所有语言，但它适用于大多数语言。
在缓存未命中/命中，管道等方面存在一些复杂性，但基本上是它的恒定时间。
虽然列表不是这种情况。 一些List实现为不同的操作提供不同的性能特征。
扩大复杂性：
问题是“大型arrays的访问速度是否会变慢”。 正确答案是“是”。
它将根据访问顺序保留O（1），但实际访问可能需要相当长的时间。 例如，如果数组的大小导致您获得缓存未命中（因此数据需要从主内存提取到处理器的缓存）和/或内存分页问题（因此数据需要从磁盘获取），它会变慢，尽管是任何大型数据集的属性，不是特定于数组。
对于大多数情况，差异不值得担心。 在您开始担心缓存未命中之类的问题之前，我们正在谈论相当重的优化。 但是，正如这个问题所示，值得注意这些事情：
为什么处理排序数组比处理未排序数组更快？
由于处理器工作方式的细节，表面上看起来无关紧要的细节（对数组进行预排序）应该总是花费相同的时间运行五倍。