嵌套循环的大 O 复杂度

Question

for (i = 0; i < 2*n; i += 2) 
{
  for (j=n; j > i; j--)
    //some code that yields O(1)
}

我认为以上会产生 n*log(n) 但我看到另一个消息来源说它真的是 n^2 复杂的大哦。请向我解释它是什么以及我将来如何处理此类问题。

Answer 1

由于大 O 是上界，因此 N * N 将始终 <= N^2，导致 O(N*2)。答案正确

Answer 2

您有一个依赖于 n 的循环，在该循环内您有另一个也依赖于 n 的循环，因此得到的 O 是 O(n*n) 即 O(n^2).

Big O 仅提供算法增长率的上限。因此，所有常数因子都被丢弃。

Big O Complexity for nested loop