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

Question

根据；破解编码面试"；Gayle Laakmann McDowdell的书一个类似的循环

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

具有CCD_ 1的运行时间。这是因为它是从N(N-1)/2减少的。这本书列举了"；整数之和"；，其中规则是CCD_ 3作为证据。

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

1, 2, 3, 4

并且将低值与高值配对；

1 + 4 = 5

2 + 3 = 5

结果5 = 4 + 1因此为N + 1由于我们已经从序列中创建了两个组，我们希望乘以N的一半长度：
O(n^2)0

我似乎无法应用这种逻辑，将低位和高位数字加在循环创建的数字上，得到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。