时间戳

首页 > 解决方案 > 内循环从与整数和的 i + 1 关系开始

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

问题描述

根据 Gayle Laakmann McDowdell 的“Cracking the Coding Interview”一书，这样的循环

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衍生的？

标签： big-o

解决方案

你为什么要配对数字？这真的比这简单得多。让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。

推荐阅读