java - 算法复杂度 : Is it the same to iterate an array from the start than from the end?

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) ？我对么？

我还被问及 ArrayList 与 java 中的其他集合(例如 LinkedList)相比的复杂性。

谢谢。

Answer 1

由于 CPU 预取特性可能会有所不同。

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

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

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