java - 嵌套循环的大 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

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

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