英文:
Time complexity and Gauss Sum Identity in Java Nested Loops
问题
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 是如何起作用的？这与内循环有什么关系？
英文:
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;
}
Given the method, we were told that the inner loop can be summarized using Gauss's sum identity, and as such, the complexity in polynomial form is
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
I don't really understand this calculation. I get that c_1 * n is the array initialization which is O(n) in Java, and that c_2 * n would be the outer loop, but how does the sum up from 1 to n-1 work here and how is that related to the inner loop?
答案1
得分: 1
忽略你代码片段中的语法错误，内部循环从 0 执行到 i，其中 i 在每次执行 for 循环时递增。这给出了和值 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。
英文:
Ignoring the syntax errors in your code snippet, the inner loop runs from 0 to i, where i increases each time the for is executed again. This gives the sum 0 + 1 + 2 + ... + n.
Now this sum was calculated by the young Gauss in the following way (for even n, but a similar construction works for odd n):
1 + n = n+1
2 + (n-1) = n+1
3 + (n-2) = n+1
...
n/2 + n/2+1 = n+1
So in total there are n/2 lines with a sum of n+1 each. This gives the result n*(n+1)/2
答案2
得分: 0
使用嵌套循环和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次。外部循环控制变量可用于控制循环的次数，更重要的是，它可用于控制内部计算的上限。
英文:
Use nested loops and the code from CPS 150 Lab Project 19 (a childish sum) to produce the output below. The outer loop control variable can be used to help display the output the inner loop.
The sum of positive integers from 1 to 1 is 1
The sum of positive integers from 1 to 2 is 3
The sum of positive integers from 1 to 3 is 6
The sum of positive integers from 1 to 4 is 10
The sum of positive integers from 1 to 5 is 15
... output for integers 16 to 99
The sum of positive integers from 1 to 100 is 5050
Because we already have a program that computes 1 + 2 + ... + n for any positive integer n, we can embed that code in a second outer loop that loops 100 times. The outer loop control variable can be used to control the number of times we loop and more importantly, it can be used to control the upper limit of the inner computation.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论