这个 for 循环 for (int j = i; j < n; j++) 的复杂度是多少？

Question

第二个 for 循环的复杂度是多少？会是ni吗？根据我的理解，第一个 for 循环将执行 n 次，但第二个 for 循环中的索引设置为 i 。

//where n is the number elements in an array
for (int i = 0; i < n; i++) {
 for (int j = i; j < n; j++) {
   // Some Constant time task
 }
}

Answer 1

如果您尝试将其可视化为一个矩阵，其中线表示i，每列表示，j您会发现这与边形成了一个三角形n

示例为n4

0 1 2 3
  1 2 3
    2 3
      3

内循环的（平均）复杂度为 n/2，即 O(n)。总复杂度为 n*(n+1)/2 或 O(n^2)