algorithm - 这个算法的 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 将是 O(N^3)。

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

我说的对吗？

Answer 1

while循环 z对于 <n 的每次执行，累积起来只会运行一次(for 次)循环 y , 自 z仅在 for 的外部范围内重置循环 y .因此，“内部范围”的粗略上限循环计数是沿着 n*(n+n) 行的。 (在 O(n^2) 中)而不是 n*n*n . W.r.t.计算复杂度，我们不妨考虑while循环 z作为 for 的循环 parallell循环 y ，而不是一个 嵌套 在 for 中循环 y .

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

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