我有两个变体来做一个简单的问题。问题很简单我们必须将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个或更多)嵌套循环,如果有的话,要小心放置,否则会不会影响性能?
您的第一种方法是一段时间内最好的方法,直到您学习了一些非常疯狂的算法为止(FFT或快速傅立叶变换将可以在O((m+k)log(m+k))
中进行,但这非常先进)。第二种方法具有相同的时间复杂度,但要追踪起来要困难得多。
不是影响您的时间复杂度的循环次数,而是相对于问题范围执行的循环次数。在第二种方法中,您只有一个循环,但要补偿该循环运行nm
次。