big-o - 带有依赖于外循环的内循环的嵌套循环的大 o 表示法

Question

我只是在学习大 O 表示法，我对嵌套循环感到困惑：

for (int x = 0; x < n; x++)
   for (int y = 0; y < n; y++)
      for (int z = 0; z < y; z++)
         anything();

据我了解，上面的内循环执行 n(n+1)/2 次，第二个循环执行 n 次，第一个循环执行 n 次。这不应该意味着大 O 是 nxnxn(n+1)/2 = O(n^4) 吗？为什么第二个循环不包含在大 O 公式中？

Answer 1

问题是：anything()作为函数的调用频率是多少n？

上面的内循环执行 n(n+1)/2 次

不，内部循环执行 y 次（每次输入），并且 y 平均 n/2。

所以方程是 n * n * n/2 = O(n^3)。

Answer 2

大 O 表示法是表示算法的上限。因此，如果基于循环的算法运行 n²+n 次，我们仍然用大 O 表示法表示为 O(n²)。有关更详细的说明，请参阅本文。