当前位置: 首页 > article >正文

【数据结构】2算法及分析

0

章节

1.4到1.5小节。

掌握算法概念、特性、描述、算法性能时间复杂度和空间复杂度;

理解递归含义?

掌握实现递归的条件和时机;

应用简单递归问题的算法设计;

重点

算法概念与特征,算法表示;

难点

算法的分析与算法设计;

递归算法的理解与使用;

作业或思考题

作业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.


http://www.kler.cn/a/584242.html

相关文章:

  • Oracle 查询数据库对象的DDL语句
  • HarmonyOS Next 全栈开发深度解析:从架构设计到分布式应用实战
  • 面试之《什么是流式渲染》
  • 微店平台商品关键字搜索接口调用指南:Python代码实现与实战解析
  • Qemu 详解与 ARM 虚拟机搭建指南
  • Vue3计算属性深度解析:经典场景与Vue2对比
  • Python 进程与线程-分布式进程
  • 工作记录 2017-01-09
  • React Next项目中导入Echart世界航线图 并配置中文
  • Flink 中RocksDB 为什么将每个键和值的限制为 2^31 字节
  • SpringCloud带你走进微服务的世界
  • 零信任架构实战手册-企业安全升级
  • 使用 Excel 实现绩效看板的自动化
  • 2024 年第四届高校大数据挑战赛-赛题 A:岩石的自动鉴定
  • css基本功
  • 手写svm primal form形式
  • kafka连问
  • 华为重拳出击!华为重拳出击!华为重拳出击!
  • Postman下载安装及简单入门
  • unity基础——地面(Physic Material)