内循环从与整数总和的 i + 1 关系开始

Question

根据盖尔·拉克曼·麦克多德尔 (Gayle Laakmann McDowdell) 的“破解编码面试”一书，这样的循环

for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {

    }
}

运行时间为O(n^2)。这是因为它是从 N(N-1)/2 减去的。书中给出了“整数求和”的例子，其中的规则是N(N+1)/2作为证据。

我想我从书中的例子中理解了 N(N+1)/2 是如何工作的。你得到一系列数字：

1, 2, 3, 4

并将低值与高值配对；

1 + 4 = 5

2 + 3 = 5

结果 5 = 4 + 1 因此 N + 1 因为我们已经从系列中创建了两个组，所以我们想乘以 N 的一半长度：
N + 1 * N/2

我似乎无法将这种将低数和高数添加到循环创建的数字并得到 n - 1 的逻辑。如果 N 为 5，则内部循环将运行

4 (times), 3 (times), 2 (times), 1 (time)

有了这些递减的数字，我看不出上面的配对规则如何符合这个得到 n - 1？有配对规则吗？ n - 1是怎么推导出来的？

Answer 1

你为什么要配对数字？它真的比那更直接。让n = array.length.

内循环在外循环的第一次迭代中有 n-1 次迭代，然后在外循环的第二次迭代中有 n-2 次迭代等。因此总步数为 (n-1) + (n-2) + ... + 1。当然是n(n-1)/2.

更新

我觉得很明显1 + 2 + ... + n = n(n+1) / 2从高中数学。但这里有一个解释。

您可以使用数学归纳法形式化地证明结果。但是你也可以给出一个直观和非正式的推导（这就是你所说的“配对”）——故事是年轻的卡尔·弗里德里希·高斯在上小学时想出来的：

1     +   2   + ... + (n-1) +   n   = x
n     + (n-1) + ... +   2   +   1   = x  (just the first line in reverse)
(n+1) + (n+1) + ... + (n+1) + (n+1) = 2x (adding the first two lines)
                             n(n+1) = 2x (counting the (n+1)'s)
                           n(n+1)/2 = x  (dividing both sides by 2)

现在如果我们只想数到 n-1 怎么办？如果你愿意，你可以再次使用相同的技巧来导出总和：

  1   +   2   + ... + (n-2) + (n-1) = x
(n-1) + (n-2) + ... +   2   +   1   = x  (just the first line in reverse)
  n   + n     + ... +   n   +   n   = 2x (adding the first two lines)
                             (n-1)n = 2x (counting the n's)
                           n(n-1)/2 = x  (dividing both sides by 2)

但实际上这太乏味了。既然你知道 1 + 2 + ... + n = n(n+1)/2，你可以只用 n-1 代替这个公式中的 n 并立即得到 n(n-1)/2.

内循环从与整数总和的 i + 1 关系开始

Inner Loop starts at i + 1 relationship to sum of integers

big-o

更新