确定 "for" 循环的大 O 复杂度。

Question

我有 3 个问题无法确定 Big O 的复杂性。

A.

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

我想说n³因为第一个循环是n²里面是n.

乙。

int x = 0;
for ( int y = 1; y <= n; y++)
   for ( int z = i; z <= n; z += 3)
      x++;

我想说大 O(n)，因为外部循环是 N 而内部我认为是大 O(3)。

C。

for ( int x = 1; x <= n; x++)
    for ( int y = n; y > 0; y /= 2)

这个一直让我很困惑。我认为内部循环是 Logn，因为每次它是运行时都除以 2。外面看起来只是 b n，那么这是 Big O (nlogn) 还是 Big O(logn)？

谢谢。

Answer 1

对于第一个，A:

您需要了解内部循环总共进行了多少次迭代。那么内循环有多少次迭代呢？它将首先有 1，然后是 2，然后是 3，直到 N^2。所以我们得到：

$T(N)=1+2+3+\dots+N^2-2+N^2-1+N^2=\frac{N^2(N^2+1)}{2}\Rightarrow O(n^4)$

下一个，B:

再次，我们看看内部循环执行了多少次迭代：

它每次运行相同的迭代次数，即n次。并且每次迭代 n 的三分之一。所以我们得到：

$T(N)=N\cdot\frac{1}{3}N\Rightarrow O(n^2)$

最后一个，C

同样，内部循环计数：

它自己迭代 $\log_2n$ 。但它做了 n 次。所以我们得到：

$T(N)=n\cdot\log_2n\Rightarrow O(n\cdot \log n)$

希望对您有所帮助，如有不明之处请告诉我：

为了进一步理解这个话题，我推荐this site。

Answer 2

关于 A 是 O(n^3)，这是比 O(n^4)

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

循环 z。 z 只会达到 y

的当前值

y=1
z: no loop

y=2
z: 1

y=3
z: 1 2

y=4
z: 1 2 3

...

y=15
z: 1 2 3 4 5 6 7 8 9 10 11 12 13 14

所以内层循环有y-1步n从1到25（=n^2）的每一步。

所以，我会说它是 T(N) = N^2 * (1 + 2 + 3 + 4 + ... + (N-1))，也就是 O(n^3)，比另一个答案中提到的 O(n^4) 更低。