在这两个循环之间，哪个代码更有效

Question

代码A:

for (int i = 0; i < n; i++) {
arrayB[i] = 1;
for (int j = 0; j < n; j++) {
arrayB[i] *= arrayA[j];
}
arrayB[i] /= arrayA[i];
}

代码B:

int i = 0;
int j = 0;
while (i < n) {
if (j == 0)
arrayB[i] = 1;
if (j < n) {
arrayB[i] *= arrayA[j];
j++;
continue;
}
arrayB[i] /= arrayA[i];
j = 0;
i++;
}

我知道嵌套循环的时间复杂度为O(n^2(，常规循环的时间复杂性为O(n(，但如果我没有错，两个循环的迭代次数不是相同吗？如果是，为什么while((循环比嵌套的for((循环更有效？

如果两者具有相同的时间复杂性，那么使用哪种循环结构更好？

Answer 1

第二个也是一个嵌套循环，您只是通过扩展它来混淆它。

如果您以等效的while形式编写for版本，

int i = 0;
while (i < n)
{
arrayB[i] = 1;
{
int j = 0;
while (j < n)
{
arrayB[i] *= arrayA[j];
j++;
}
arrayB[i] /= arrayA[i];
}
i++;
}

并使用else而不是continue、将while版本重新排列为可读性稍高的等效版本

int i = 0;
int j = 0;
while (i < n) {
if (j == 0)
arrayB[i] = 1;
if (j < n) { /* Executes once for each 0 <= j < n */
arrayB[i] *= arrayA[j];
j++;
}
else /* j == n; end of 'j loop' */
{
arrayB[i] /= arrayA[i];
j = 0; /* Restart the 'j loop'. */
i++;
}
}

很明显，他们以几乎完全相同的方式完成了完全相同的工作量。唯一的区别是，你的while变体非常不可理解。

最好的版本是(当然(不试图隐藏"；用于循环"；自然界的事物背后有一堆难以纠缠的东西在跳来跳去。

也就是说，实际上最好的版本在线性时间内运行——你为arrayB的每个元素计算相同的arrayA乘积。

如果不将arrayB[i]用于中间结果和最终结果((，这一点会变得更加明显

for (int i = 0; i < n; i++) {
int product = 1;
for (int j = 0; j < n; j++) {
product *= arrayA[j];
}
arrayB[i] = product / arrayA[i];
}

现在很明显，内循环计算的乘积对于所有i都是相同的，并且可以从外循环中吊出。

今天的课程总结：

1. 说明你的意思的直接代码很少能通过尝试聪明来改进
2. 将一个变量用于多种目的可能会隐藏宝贵的改进机会