在一次面试中，我被要求提供以下信息:
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] array = new int [10000];
for (int i = 0; i < array.length; i++) {
// do calculations
}
for (int x = array.length-1; x >= 0; x--) {
// do calculations
}
}
从末尾或从头开始迭代数组是否相同？据我了解，这将是相同的，因为复杂性是恒定的，即 O(1) ？我对么？
我还被问及 ArrayList 与 java 中的其他集合(例如 LinkedList)相比的复杂性。
谢谢。
最佳答案
由于 CPU 预取特性可能会有所不同。
根据计算理论，在任一方向上循环都没有区别。但是，根据运行代码的 CPU 使用的预取器类型，实践中会有一些差异。
例如，Sandy Bridge Intel 处理器有一个预取器，它只对数据进行转发(而指令可以双向预取)。这将有助于从一开始就进行迭代(因为 future 的内存位置被预取到 L1 缓存中)，而从末尾进行迭代将导致很少甚至没有预取，因此对 RAM 的访问更多，这比访问任何 CPU 缓存都慢得多.
在此 link 中有关于前向和后向预取的更详细讨论。 .
关于java - 算法复杂度 : Is it the same to iterate an array from the start than from the end?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41655437/