嵌套循环对单循环的编译器内存分配差异

Question

我有两个变体来做一个简单的问题。问题很简单我们必须将pow2的每个元素与pow3的每个元素相乘，其中pow2和pow3都是带有整数的数组。

该代码在javascript（Node.js）中。我在这里将两个数组都保留为空，我们可以在运行时用不同的数字填充它们。

第一个：-

let pow3 = [], pow2 = [];
for (let i = 0; i < pow3.length; ++i) {
    for (let j = 0; j < pow2.length; j++) {
        let result = pow3[i] * pow2[j];
    }
}

第二：-

let pow3 = [], pow2 = [];
let j = 0, i = 0;
for (;;) {
    let result = pow3[i] * pow2[j];
    if (++i === pow3.length) {
        i = 0;
        j++;
    }
    if (j === pow2.length)
        break;
}

现在时间复杂度是相同的，如果在两个方法中都计算为O（m * n）m和n是数组的长度，但是我想知道的是两种情况下的运行时间都不同，因为approach-1有2个循环（嵌套），而approach-2有1个单一循环。我想知道编译器将如何区别对待它们。

此外，我们可以用一个单独的循环替换多个（2个或更多）嵌套循环，如果有的话，要小心放置，否则会不会影响性能？

[我认为大多数人都将这个问题视为简单性问题，所以让我对此进行更多说明。在这里，我们谈论的是循环优化（与机器无关），在这方面也是如此[[Loop Jamming，因为当存在嵌套循环时，参考位置很差，这导致更多的时间消耗执行时（理论上）进行存储器切换。但是由于资源不足，我不确定这是否会影响上述情况。

因此，如果有人从这个角度回答（编译器优化），我将非常感激。

Answer 1

您的第一种方法是一段时间内最好的方法，直到您学习了一些非常疯狂的算法为止（FFT或快速傅立叶变换将可以在O((m+k)log(m+k))中进行，但这非常先进）。第二种方法具有相同的时间复杂度，但要追踪起来要困难得多。

不是影响您的时间复杂度的循环次数，而是相对于问题范围执行的循环次数。在第二种方法中，您只有一个循环，但要补偿该循环运行nm次。