algorithm - 确定这些不同循环的大 O 运行时间？

Question

确定这些不同循环的大 O 运行时间？

for i = 1 to n {
  ...
  for  j = 1 to 2*i {
    ...
    k = j;
    while (k>=0) {
      ...
      k = k-1;
    }
  }
}

我发现答案是 O(n^3)，因为三个循环彼此嵌套，我的答案正确吗？

Answer 1

作为一种启发式方法，这是正确的，但这种启发式方法可能会让您误入歧途。可以找到内循环数的确切公式。

对于每个 j，k 从 j 向下运行到 0，包括 0，因此内部循环运行 j+1 次。

对于每个 i，j 从 1 运行到 2*i，因此对于 i=1，内部循环运行 1+1 和 2+1 次，然后对于 i=2，运行 3+1 和 4+1 次，等等。我希望您能看到，对于每个 i，内部循环都比第 (2i+1) 个三角数少运行一个。第 n 个 triangular number是 n(n+1)/2，所以对于每个 i，我们得到一个

(2i+1)(2i+1+1)/2 - 1

简化为

2 * i**2 + 3 * i

对于每个 n，i 从 1 到 n，所以我们只对从 1 到 n 的最后一个表达式求和。这给了我们前 n 个平方数的总和加上第 n 个三角数的三次之和的两倍。 the sum of the first n square numbers 的公式是

n**3/3 + n**2/2 + n/6

所以我们简化

2*(n**3/3 + n**2/2 + n/6) + 3*(n*(n+1)/2)

我们得到

2/3 * n**3 + 5/2 * n**2 + 11/6 * n

这显然是 O(n**3)，所以您的启发式是正确的。

我用一些简单的 Python 代码检查了最终的表达式。