嵌套循环的时间复杂度

Question

嵌套循环的时间复杂度

我需要计算以下代码的时间复杂度：

for (i = 1; i <= n; i++)
{
  for(j = 1; j <= i; j++)
  {
   // Some code
  }
}

是吗O(n^2)?

Answer 1

解释这一点的一个快速方法是将其形象化。如果i和j都是0到N，则很容易看到O(N^2)。O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O在这种情况下，它是：O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O这是N^2的1/2，仍然是O(N^2)。

Answer 2

实际上，它是O(n^2)。还请参见具有相同运行库的非常类似的示例。这里.