algorithm - 对两个相关循环的复杂性感到困惑？

Question

for(i=1; i < n; i++){
   for(j=1; j <= i; j++){
         statement1;
   }       
}

• 外层循环 = O(N)
• 内循环 = N(N-1)/2
• 总计 = N*N(N-1)/2 = N^3

似乎 n^3 是这些嵌套循环的复杂性。但根据书籍，它的复杂性是 n^2 来自 N(N-1)/2 。

Answer 1

唯一有趣的是计算频率statement1将被执行。

因此，请注意类似

for (int i = 0; i < 2; i++)
    for (int j = 0; j < 3; j++)
        statement1;

触发器 2 * 3 = 6处决。因此，您可以计算每次外循环迭代内循环执行的频率。

但是，在您的示例中，您犯了一个错误，将外循环的迭代次数乘以内循环的总迭代次数，而不是每次外循环迭代次数的迭代次数强>.

在上面的示例中，它类似于 2 * 6 = 12而不仅仅是 2 * 3 = 6 .

---

让我们仔细看看您的具体示例中发生了什么。外循环触发 n内循环的迭代。内部循环首先产生 1迭代。在外循环的下一次迭代中，它将产生 2迭代，然后 3等等。

因此，您总共将收到 1 + 2 + ... + n = (n^2 - n)/2内循环的迭代。再次注意“总计”。所以statement1将总共 执行(n^2 - n)/2次。外循环迭代已被考虑在内循环总运行的计算中，没有额外的乘法。

---

(n^2 - n)/2显然是在O(n^2)由于其渐近复杂性。直觉上只有最大的因素起作用，我们可以通过估计 <= 来丢弃其他东西。 .

(n^2 - n)/2
    <= n^2 - n
    <= n^2 in O(n^2)