数据结构2算法及分析
【数据结构】2算法及分析
0
章节
１．４到1．５小节。
掌握算法概念、特性、描述、算法性能时间复杂度和空间复杂度；
理解递归含义？
掌握实现递归的条件和时机；
应用简单递归问题的算法设计；
重点
算法概念与特征，算法表示；
难点
算法的分析与算法设计；
递归算法的理解与使用；
作业或思考题
作业2：算法设计与表达
内容达成以下标准(考核点)：
理解与陈述算法概念；
理解并设计与表达算法：设计算法，使用工具表达，分析算法
算法设计与实现作业
摘要: 本文旨在为求1+（1+2）+（1+3）+（1+2+4）+（1+3+5）+….+（1+2+…+2n)+（1+3+5+…+2n-1)的和,设计算法，并分别使用自然语言、N-S图，伪代码来表示。分析算法的时间和空间效率, 和评价算法，然后使用java 完成算法的实现。
关键词： 算法设计；评价；Java实现；
abstract
The purpose of this article is to design an algorithm to calculate the sum of the series 1 + (1+2) + (1+3) + (1+2+4) + (1+3+5) + … + (1+2+…+2n) + (1+3+5+…+2n-1). The algorithm will be represented using natural language, an N-S diagram, and pseudo code. The time and space efficiency of the algorithm will be analyzed, and the algorithm will be evaluated. Finally, the algorithm will be implemented in Java.
Keywords: Algorithm Design; Evaluation; Java Implementation
1 实现方法一
1.1 算法表示
1.1.1自然语言表示
1．创建一个变量sum并将其初始化为0，用于保存总和。
2．使用for循环从1迭代到n，迭代变量i表示当前迭代的数字。
3．在每次迭代开始时，创建两个临时变量s1和s2，分别用于保存奇数项和偶数项的和，并将它们初始化为0。
4．判断i是否大于1，如果是，则计算s1的值为(i-1) * (i-1) + i，表示从1到2n-1的所有奇数的和，如果不是，则s1保持为0。
5．计算s2的值为i * i，表示从1到2n的所有偶数的和。
6．将s1和s2分别累加到总和sum中。
7．循环结束后，返回总和sum作为最终结果。
1.1.2 N-S图表示
1.1.3伪代码表示
输入：n
输出：sum // 1+（1+2）+（1+3）+（1+2+4）+（1+3+5）+….+（1+2+…+2n)+（1+3+5+…+2n-1)的和
function calculateSum(n):
sum = 0
for i from 1 to n:
s1 = 0
s2 = 0
if i > 1:
s1 = (i-1)^2 + i
s2 = i^2
sum += s1 + s2
return sum
1.2 算法分析
时间复杂度分析：外层循环迭代n次，所以时间复杂度为O(n)。内部计算s1和s2的操作是常数时间的，不会随输入规模变化，因此对时间复杂度没有影响。
空间复杂度分析：算法使用了常数个变量来保存中间结果，所以空间复杂度为O(1)，即为常数级别。不会随输入规模变化。
1.3 算法实现
public class Algorithm {
public static int calculateSum(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
int s1 = 0;
int s2 = 0;
if (i > 1){
s1 = (i-1) * (i-1) + i;//单独的和, 偶数项
}
s2 = i * i;//单独的和, 奇数项
sum += s1 + s2;
}
return sum;
}
public static void main(String[] args) {
int n = 4;
int result = calculateSum(n);
System.out.println("当n=" + n + "时，sum=" + result);
}
}1.4 算法总结
该算法是一个简单直观的解决方案，它通过循环迭代计算每一项的和，并将其累加到总和中。由于只有一个循环，算法的时间复杂度是线性的，具有较好的效率。同时，算法的空间复杂度也是常数级别的，节省了内存的使用。总体而言，这个算法是一个有效且可行的解决方案。
2实现方法二
2.1 算法表示
2.1.1自然语言表示
1．初始化两个数组s1和s2，长度为n。
2．对于从1到n的每个数i：
如果i大于1，计算s1[i-1]的值为 (i-1) * (i-1) + i。
计算s2[i-1]的值为 i * i。
3．定义变量sum并初始化为0。
4．对于数组s1和s2的每个索引i：
将s1[i]和s2[i]的值累加到sum上。
5．返回sum作为结果。
2.1.2N-S图表示
2.1.3伪代码表示
输入：n
输出：sum // 1+（1+2）+（1+3）+（1+2+4）+（1+3+5）+….+（1+2+…+2n)+（1+3+5+…+2n-1)的和
function calculateSum(n):
s1 = new int[n]
s2 = new int[n]
for i = 1 to n:
if i > 1:
s1[i-1] = (i-1) * (i-1) + i
s2[i-1] = i * i
sum = 0
for i = 0 to n-1:
sum += s1[i]
sum += s2[i]
return sum
2.2 算法分析
时间复杂度分析：该算法的时间复杂度为O(n)，其中n是输入的参数。因为算法包含两个for循环，两个循环的迭代次数都是n。
空间复杂度分析：该算法的空间复杂度为O(n)，其中n是输入的参数。因为算法使用了两个长度为n的数组s1和s2来存储中间结果。此外，还有几个整型变量用于计算和累加过程，它们的空间占用可以忽略不计。
2.3 算法实现
public class Algorithm {
public static int calculateSum(int n) {
int[] s1 = new int[n];
int[] s2 = new int[n];
for (int i = 1; i <= n; i++) {
if (i > 1){
s1[i-1] = (i-1) * (i-1) + i; // 计算s1的值
}
s2[i-1] = i * i; // 计算s2的值
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += s1[i] + s2[i]; // 累加s1和s2的值
}
return sum;
}
public static void main(String[] args) {
int n = 4;
int result = calculateSum(n);
System.out.println("当n=" + n + "时，sum=" + result);
}
}2.4 算法总结
算法优点： 这个算法有效地解决了问题，具有线性时间复杂度，适用于大多数输入规模。它的实现相对简单，易于理解。
算法缺点： 该算法使用了额外的空间来存储两个数组s1和s2，这可能会在输入规模很大的情况下导致内存消耗较大。如果对空间效率有更高的要求，可以考虑在计算过程中动态生成s1和s2的值而不存储它们。
总的来说，这个算法是一个有效的解决方案，适用于大多数情况，但在某些特定情况下，可能需要优化空间复杂度。
总结性分析:
第二个算法的优点在于将括号内部的和分别存放在两个数组中，方便计算和累加。但是它的缺点在于需要占用较多的空间，且计算s1的时候会产生一定的重复计算。
而第一个算法则没有使用数组，而是在每次循环的过程中直接计算出s1和s2并进行累加，避免了数组带来的空间占用和计算重复的问题。但是其缺点在于代码可读性不如第一个算法。
参考文献
[1] 王红梅, 党源源, 刘冰. 数据结构–从概念到Java实现[M]. 清华大学出版社, 2019.