Java 嵌套循环中的时间复杂度和高斯和恒等式

Question

public static int[] intSum(int[] arr2) {
  int[] arr1 = new int[arr2.length];
  for (int i = 0; i < arr2.length; i++) {
    for (int j = 0; j <= i; j++) {
      arr1[i] += arr2[j];
     }
  }
  return arr1;
}

给出的方法，我们被告知可以使用高斯和恒等式来总结内环，因此，多项式形式的复杂度是

T(n) = c_0 + c_1 * n + c_2 * n + (1 + 2 + ... + (n-1)) * c_3

=> T(n) = c_0 + n * c_1 * n * c_2 * (n(n+1))/2 * c_3

这个计算我不是很懂。我知道 c_1 * n 是数组初始化，它是 Java 中的 O(n)，而 c_2 * n 将是外循环，但是 [=17= 的总和如何] 到 n-1 在这里工作，它与内部循环有什么关系？

Answer 1

忽略代码片段中的语法错误，内部循环从 0 运行到 i，其中每次再次执行 for 时 i 都会增加。这给出了总和 0 + 1 + 2 + ... + n.

现在这个和是由年轻的高斯按以下方式计算的（对于偶数 n，但类似的构造适用于奇数 n）：

1 + n     = n+1
2 + (n-1) = n+1
3 + (n-2) = n+1
...
n/2 + n/2+1 = n+1

所以总共有 n/2 行，每行总和为 n+1。这给出了结果 n*(n+1)/2

Java 嵌套循环中的时间复杂度和高斯和恒等式

Time complexity and Gauss Sum Identity in Java Nested Loops

java

time-complexity