algorithm - 嵌套循环 i=0..n-2、j=i+1..n-1 的 Big-Oh 是什么？

Question

给定以下代码：

for (int i = 0; i < n-1; ++i)
{
    for (int j = i+1; j < n; ++j)
    {
        // Do work.
    }
}

它的 Big-Oh 值是多少（超过n）？我认为它是 O(N^2) 但我不确定。

我确实在这里找到了一个类似的问题：complexity for nested loops

但我认为并不完全一样。

Answer 1

应该可以通过这种方式进行检查。

int z = 0, n = 10; // try 20 etc
for (int i = 0; i < n-1; ++i)
{
    for (int j = i+1; j < n; ++j)
    {
        z++;
    }
}

现在，检查 z 的值。

With n = 10; z becomes 45
With n = 20; z becomes 190
With n = 40; z becomes 780

n翻倍导致z变为其值的约 4 倍。因此，它大约是O(n^2)。

Answer 2

是的，就是这样O(N^2)。在外循环的开始和结束时配对内循环的迭代，如下所示：

内部循环将执行...

• N-1外循环第一次迭代的1时间和最后一次迭代的时间
• N-2外循环第二次迭代的2次数，倒数第二次迭代的次数
• N-3外循环第三次迭代的次数，以及3第三次到最后一次迭代的次数
• ... 等等; 你会有这样的N/2配对；当N是奇数时，最后一对是不完整的。

您可以看到每一对执行总N次数，并且您有N/2这样的对，总共执行N*(N-1)/2次数。

公式的推导方式是推导算术级数与 的公差之和的公式1。

Answer 3

有条不紊地，使用 Sigma 表示法（经过经验验证），您可以获得准确的迭代次数加上增长复杂度的顺序：