time-complexity - 这个嵌套循环的时间复杂度是多少？

Question

我偶然发现了一个循环，我不确定时间复杂度是多少。它是以下循环：

for(i = 1; i <= n^2; i++){
   for(j = 1; j <= i; j++) {
      //some elementary operation
   }
}

我会争辩说，外部 for 循环在 n^2 中运行，而内部 for 循环也将在 n^2 中运行，因为对于我们执行 n^2 - (n^2 - 1) 的外部循环的每次迭代， n^2 - (n^2 - 2),..., n^2。我在这里完全走错了方向吗？

所以时间复杂度是 n^4

标签： time-complexity

Answer 1

操作次数为：

1 + 2 + 3 + 4 + 5 + ... + n²

等于 (n² * (n² - 1)) / 2。

大 O 表示法是 O(n^4)。你是对的。