在嵌套 for 循环中使用 j= i+1 vs j = 1？

Question

我很难回答这个问题。所以我就用一个例子来说明。

假设我有以下数组：A = {5,8,1,3,2,6}，大小为 n = 6，索引为 A[0...5]。

我想运行进行某种扫描，以便在从左到右的遍历中将每个值与与其相邻的值进行比较。以下 2 个运行嵌套 for 循环的代码片段有什么区别？

// snippet 1, using i to take the first and j to take whatever is next to i.
for i <- 0 to n-2 do
    for j <- i+1 to n-1 do
       // do the scanning, comparing, etc.... 


//snippet 2 using i to take the first and j to take the second. 
for i <- 0 to n-2 do
        for j <- 1 to n-1 do
           // do the scanning, comparing, etc....

我认为它们完全相同，并且在我所做的 pen/paper 测试中找不到任何差异。有吗？

Answer 1

第一个中，j从i的下一个值开始计数。

示例：i = 1, j = 2 | i = 2, j = 3等

在第二个中，无论 i 的值如何，您都将从 1 开始计数。换句话说，变量 i 对变量 j.

没有影响

两者都有各自的用途，但这完全取决于您如何使用它们来获取数组元素。

Answer 2

好的，让我们来看看运行其中 n = 3

// snippet 1, using i to take the first and j to take whatever is next to i.
for i <- 0 to n-2 do
    for j <- i+1 to n-1 do
       // do the scanning, comparing, etc....

第一次迭代（最外层循环）：

i = 0 和 j = 1

i = 0 和 j = 2

第二次迭代：

i = 1 和 j = 2

完成！

//snippet 2 using i to take the first and j to take the second. 
for i <- 0 to n-2 do
        for j <- 1 to n-1 do
           // do the scanning, comparing, etc....

第一次迭代：

i = 0 和 j = 1

i = 0 和 j = 2

第二次迭代：

i = 1 和 j = 1

i = 1 和 j = 2

注意到代码片段 2 的第二次迭代中的差异了吗？

Answer 3

两者都构建数组元素对。定义什么是不同的对有两种不同的想法：

1) 只有包含不同元素的对才是唯一的。 (A[i], A[j]) == (A[j], A[i])

2) 如果元素的顺序不同，则一对是唯一的。 (A[i], A[j]) <> (A[j], A[i])

此外，代码段二还将 (A[i], A[i]) 视为一对（当 i == j 时），不包括 (A[0], A[0]) 和 (A[n - 1], A[n - 1])

在嵌套 for 循环中使用 j= i+1 vs j = 1？

In nested for-loops use j= i+1 vs j = 1?

algorithm

pseudocode