为什么仅更改循环计数器逻辑时使用 2 个嵌套循环、O(n^2) 复杂度、运行更快地解决两个和问题？

Question

解决 two sum 问题可以使用 O(n) 复杂度算法来实现，但是，我只是尝试了 O(n^2) 复杂度，这是使用 2 个嵌套循环检查每个第 i 个整数与每个其余整数与目标值的总和，以下是 O(n^2) 实现，对于 2 个实现，nums 是整数数组，n 是 nums 的大小，indices 是一个大小为 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;
    }
}

此实现在 140 毫秒内解决了问题。我尝试了另一种 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 是数组还是向量，它都能正常工作。

为什么仅更改循环计数器逻辑时使用 2 个嵌套循环、O(n^2) 复杂度、运行更快地解决两个和问题？

Why solving the two sum problem using a 2 nested loops, O(n^2) complexity, run much faster when only changing the loops counter logic?

c++

algorithm

localityofreference

为什么仅更改循环计数器逻辑时使用 2 个嵌套循环、O(n^2) 复杂度、运行 更快地解决两个和问题？

Why solving the two sum problem using a 2 nested loops, O(n^2) complexity, run much faster when only changing the loops counter logic?

c++

algorithm

localityofreference

为什么仅更改循环计数器逻辑时使用 2 个嵌套循环、O(n^2) 复杂度、运行更快地解决两个和问题？