为什么这个“毛毛虫算法”是O(n^2)而不是O(n^3)？

Question

为什么这个“毛毛虫算法”是O(n^2)而不是O(n^3)？

6

有人能解释一下为什么这个算法是 O(n^2) 吗？根据 this，它是 O(n^2)。

我认为它是 O(n^3) 的原因是外部循环（对于 x）运行了 n 次，内部循环（对于 y）运行了 n-1 次，在最坏的情况下，例如 A = [8, 100, 101, 102, 103, 104, 105, 106, 107]，while 循环（对于 z）将运行 n-2 次，因此总体上是 O(n^3)。

为了完整起见，A 是一个正元素排序数组，如果 A[x] + A[y] > A[z]，则三元组（x，y，z）是一个三角形。找出可以从 A 中构建多少个三角形。

        int TrianglesCount(int[] A)
        {
            int result = 0;
            for (int x = 0; x < A.Length; x++)
            {
                int z = x + 2;
                for (int y = x + 1; y < A.Length; y++)
                {
                    while (z < A.Length && A[x] + A[y] > A[z])
                        z++;
                    result += z - y - 1;
                }
            }
            return result;
        }

- dragonfly02

4个回答

2

请注意，z是在x循环内初始化的，而不是y循环内。在每个x迭代中，z最多可以增加A.length - x - 2次。

- DAle

0

关键在于 z 总共会增加到 A.Length: 例如，如果我们在第一次迭代中不幸运:

x=0, y=1，我们会让 z 从2增加到 A.Length，在随后的 y 循环中，z 将不会增加。

- Tamas Ionut

z不会有任何增量吗？z在每次迭代中都被重新初始化为x+2，因此仍然可以递增。 - dragonfly02

在后续的y循环中，它仍将在x循环中递增。 - Tamas Ionut

0

这是我对此的解释。

首先，当n很小时，你不能谈论复杂性。复杂性本身的定义是说，只有当n趋近于无穷大时，复杂性才“有意义”。例如，在一个有3个元素的数组上进行冒泡排序可能看起来像O(n)。

除此之外，关于你的算法：

变量z在x循环内部声明，而不是y循环内部，因此每次完成y循环时都不会重新初始化z。这意味着z将在每次x循环通过时仅增加到A.length一次。一旦z达到A.length，它就不会再增加了，因此它不依赖于y循环。我希望这个解释足够清晰，让你现在能够更好地理解这个问题。

- leonz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- pkacprzak · Accepted Answer

让我们仔细看一下下面的代码片段。

int z = x + 2;
for (int y = x + 1; y < A.Length; y++)
{
   while (z < A.Length && A[x] + A[y] > A[z])
      z++;
   result += z - y - 1;
}

for循环明显执行了A.length - (x+1)次，这是O(n)。然而，内部while循环总共最多执行A.length - (x+2)次，因为每次这样的执行都会增加z的值，直到while条件失败时它最多可以增加A.length - (x+2)次。同样，这最多也是O(n)。因此，这段代码的总时间复杂度可以被限制在O(n) + O(n) = O(n)。

由于这段代码对于O(n)个x值运行，因此总体时间复杂度为O(n^2)。

在字符串匹配中使用了类似的思想，例如KMP算法。