嵌套循环的时间复杂度

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)。还请参见具有相同运行库的非常类似的示例。这里.