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是外部循环，但是从1到n-1的求和是如何工作的，它与内部循环有什么关系？
2条答案
按热度按时间m1m5dgzv1#
忽略代码片段中的语法错误，内部循环从
0运行到i，每次再次执行for时，i都会增加。这给出了总和0 + 1 + 2 + ... + n。现在这个总和是由年轻的高斯以下列方式计算的（对于偶数n，但对于奇数n，类似的构造也有效）：
所以总共有n/2行，每行的和为n+1。这给出了结果n*（n+1）/2
cetgtptt2#
使用嵌套循环和CPS 150实验项目19的代码（幼稚的总和）产生以下输出。外部循环控制变量可用于帮助显示内部循环的输出。
1到1的正整数之和为1 1到2的正整数之和为3 1到3的正整数之和为6 1到4的正整数之和为10 1到5的正整数之和为15 ...整数16到99的输出1到100的正整数之和为5050
因为我们已经有了一个程序，可以对任何正整数n进行1 + 2 + ... + n的计算，所以我们可以将该代码嵌入到第二个外部循环中，循环100次。外部循环控制变量可以用来控制我们循环的次数，更重要的是，它可以用来控制内部计算的上限。