为什么使用 2 个嵌套循环 O(n^2) 复杂度来解决二和问题，当只改变循环计数器逻辑时运行得更快?

Question

解决二和问题可以使用 O(n( 复杂性算法来实现，但是，我刚刚尝试了 O(n^2( 复杂性，这是一种使用 2 个嵌套循环的朴素方法，该嵌套循环根据目标值检查每个第 i 个整数与其余每个整数的总和，以下是 O(n^2( 实现， 对于 2 个实现，nums是整数数组，n是 num 的大小，索引是一个大小为 2 的数组，用于保存 2 个整数的索引

for(int i=0; i<n; ++i)
for(int j=i+1; j<n; ++j) {
if(nums[i] + nums[j] == target) {
indices[0] = i; indices[1] = j; return indices;
}
}

此实现在 140ms 内解决了问题。我尝试了另一种 O(n^2( 方法，对于从 1 到 n-1 的每个 k 值，根据目标值检查第 i 个整数和第 (i+k( 个整数的总和，以下是实现，

for(int k=1; k<n; k++)
for(i=0; i<n-k; i++) {
int j=i+k;
if(nums[i] + nums[j] == target) {
indices[0] = i; indices[1] = j; return indices;
}
}

如您所见，相同的循环体，但运行速度更快，运行时间为 8 毫秒。为什么？它与空间局部性有关吗？

Answer 1

一个公平的比较是让两个程序执行到最后，但仍然找不到索引。从外观上看，您正在针对存在答案的案例进行测试。当然，在这种情况下，我们寻找答案的顺序非常重要。

例如，当唯一的答案是{n - 2, n - 1}时，第一个代码需要 O(n^2( 操作才能找到它，而第二个代码在 O(n( 中找到它。要生成的代码：

std::fill (&num[0], &num[0] + n, 0);
target = 2;
num[n - 2] = 1;
num[n - 1] = 1;

相反，当唯一的答案是{0, n - 1}时，第一个代码在O(n(中找到它，而第二个代码将采取O(n^2(步骤。要生成的代码：

std::fill (&num[0], &num[0] + n, 0);
target = 2;
num[0] = 1;
num[n - 1] = 1;

&num[0]的东西是确保它无论num是数组还是向量都能正常工作。