算法复杂性：从头迭代数组和从末尾迭代数组是否相同？

Question

在一次采访中，我被问到以下问题：

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) ，所以它会是一样的？我对么？

我还被问到与 Java 中的其他集合（例如 LinkedList）相比，ArrayList 的复杂性。

谢谢你。

Answer 1

由于 CPU 预取特性，可能存在差异。

根据计算理论，在任一方向上循环之间没有区别。但是，根据运行代码的 CPU 所使用的预取器的类型，在实践中会存在一些差异。

例如，Sandy Bridge Intel 处理器有一个预取器，它只处理数据（而指令可以双向预取）。这将有助于从一开始的迭代（因为未来的内存位置被预取到 L1 缓存中），而从末尾迭代将导致很少或没有预取，因此对 RAM 的更多访问比访问任何 CPU 缓存慢得多.

在此链接中有关于前向和后向预取的更详细讨论。