嵌套循环的大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)ie O(n^2).

大O只是提供了一个上界上的生长速率的算法.因此,所有常数因子都被丢弃.