这个算法的 Big oh 是 n^3 而不是 n^2

Question

def triangles(A):
  n = len(A)
  result = 0
  for x in xrange(n):
    z=x+2
    for y in xrange(x + 1, n):
      while (z < n and A[x] + A[y] > A[z]):
        z += 1
      result += z - y - 1
  return result

这是codility(https://codility.com/media/train/13-CaterpillarMethod.pdf)

中解决方案的一个例子

在手册中，他们声称这个算法的大O是O(N^2)

我认为 big-Oh 是 O(N^3)，因为最坏情况的迭代将是

(n-1)(n-2) + (n-2)(n-3) + ..... + 1*0

所以我认为它的大哦将是 O(N^3)。

谁能解释一下为什么这个算法的大O是O(N^2)？

我说的对吗？

Answer 1

对于x的每个值，z最多只能增加n次。一旦 z 等于 n，则在再次增加 x 之前，内循环不可能迭代。因此 n x 的值和 n 内循环的迭代给出 n^2.

Answer 2

while 遍历 z 的循环，每次执行累积起来只会运行一次（<n 次） for 循环的 y，因为 z 仅在 for 循环 [=15] 的外部范围内重置=].因此，"inner scope" 的粗略上限循环计数是沿着 n*(n+n) 行（在 O(n^2) 中）而不是 n*n*n。 W.r.t。计算复杂度，我们不妨将 z 上的 while 循环视为并行到 y 上的 for 循环的循环，而不是在 y.

的 for 循环中嵌套

即，与例如相同的复杂性：

def triangles(A):
  n = len(A)
  result = 0
  for x in xrange(n):
    z=x+2
    while (z < n)
      z += 1
    for y in xrange(x + 1, n):
      ...
  return result

这个算法的 Big oh 是 n^3 而不是 n^2

Is this algorithm's Big oh is n^3 rather than n^2

algorithm

big-o