数据结构与算法--算法和算法分析

news/2024/5/30 2:53:43/文章来源:https://blog.csdn.net/weixin_74314406/article/details/136710401

算法与数据结构之间存在密不可分的关系。简单来说,数据结构是存储和组织数据的方式,而算法则是操作和处理这些数据的方法。

首先,数据结构为算法提供了基础。算法是解决问题的步骤和流程,通过对数据结构进行操作,算法可以实现对数据的增删改查等操作。不同的数据结构特性影响算法的操作方式,例如,如果算法需要对一个有序数组进行搜索,那么它需要知道数组的有序性质,以便采用二分搜索的方式进行操作。同时,对于同一问题,不同的数据结构可能会导致不同的算法实现方式,因此在选择数据结构时必须考虑算法的复杂度和效率。

其次,算法对数据结构的优化和选择也有重要影响。算法可以通过优化数据结构来提高其性能,例如,通过使用合适的排序算法,可以减少排序时间。反过来,数据结构的设计也需要考虑到算法的实现和运行效率。一些排序算法需要随机访问数组元素,而另一些算法则需要在不同的时间点插入和删除元素,这些需求都会影响数据结构的选择。

程序= 数据结构+算法


算法的五个重要特性包括:

  1. 有穷性:算法必须能在执行有限个步骤之后终止。也就是说,一个算法在执行过程中不能无限循环,每个步骤都应该在有限时间内完成
  2. 确切性:算法的每一步骤必须有确切的定义,不能有二义性。这意味着算法的每一步都是清晰、明确的,不存在模糊或不确定的地方。
  3. 输入:一个算法有0个多个输入,以刻画运算对象的初始情况。这些输入是算法开始执行前所必需的,它们为算法提供了初始数据和条件。
  4. 输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。输出是算法执行完毕后得到的结果,是算法的主要目的。
  5. 可行性算法中执行的任何计算步骤都应该是可以执行的,即每个计算步都可以在有限时间内完成。这意味着算法所描述的操作都是实际可行的,可以通过已经实现的基本操作执行有限次来实现。

算法设计要求:

  1. 正确性与健壮性
    • 算法必须能够准确执行其预定功能,对于所有合法的输入都能产生正确的输出结果。
    • 算法应当具有健壮性,即能够合理处理异常情况、错误输入或非法数据,并给出相应的提示或处理结果,确保算法的稳定性和可靠性。
  2. 可读性
    • 算法设计应易于阅读和理解,使用清晰、简洁的语言和符号表达算法的逻辑。
    • 算法的结构应合理,逻辑应清晰,方便他人理解算法的工作原理和实现过程,便于后续的调试、维护和升级。
  3. 效率
    • 算法设计应追求高效,包括时间效率和空间效率
    • 在满足正确性的前提下,应尽量减少算法的执行时间和所需的存储空间,提高算法的性能。
    • 可以通过优化算法的时间复杂度和空间复杂度来实现高效的算法设计。
  4. 可维护性
    • 算法设计应考虑可维护性,使算法易于修改和扩展
    • 算法应具有模块化和结构化的特点,便于对各个部分进行单独的修改和替换。
    • 同时,算法的设计应考虑到未来的变化和升级需求,能够方便地添加新功能或修改现有功能,以适应不同的应用场景和需求。

        算法时间效率的度量:

        算法的时间效率可以依据算法编制的程序在计算机上执行进行的消耗的时间来度量。

        1.事后统计:要求将算法编程程序(计算机的软硬件会影响算法的优劣)

        2.事前分析:只能进行估算(更多用这个)

算法时间 = Σ每条语句频度*该语句执行一次的所需时间

假设每条语句执行的所需的时间均为单位时间,所以对算法运行时间就转化为讨论算法中所有语句执行次数,也就是频度之和。

例:

for(i=1;i<=n;i++){for(j=1;j<=n;j++){c[i][j]=0;for(k=0;k<n;k++)c[i][j]=c[i][j]+a[i][k]*b[i][k];}

这个代码段包含三个嵌套的循环,用于计算一个二维数组 c 的元素,其中 c[i][j] 是通过矩阵乘法得到的,即 c[i][j] 是由矩阵 a 的第 i 行与矩阵 b 的第 j 列的点积计算得出的。

首先,我们来分析每个循环的迭代次数:

  1. 外层循环 i 迭代 n 次(从 1 到 n)。
  2. 中层循环 j 也在每次外层循环 i 的迭代中迭代 n 次(从 1 到 n)。
  3. 内层循环 k 在每次中层循环 j 的迭代中迭代 n 次(从 0 到 n-1)。

因此,总的迭代次数是 n(外层循环)* n(中层循环)* n(内层循环)= n^3

由于内层循环中的操作(即 c[i][j]=c[i][j]+a[i][k]*b[i][k];)是常数时间的,所以整个算法的时间复杂度是 O(n^3)。这是矩阵乘法的一个常见时间复杂度,特别是在没有使用任何优化技术(如Strassen算法或并行计算)的情况下。

所以,这个代码段的时间渐进复杂度是 O(n^3)

 

 

一般情况下:时间复杂度可以直接找循环嵌套最深的

算法时间复杂度的渐进表示法:

我们仅仅需要比较数量级(数量级越大越不好)

算法的渐进时间复杂度是对算法的时间效率的度量,即分析一个算法执行所需要的时间。它表示随问题规模n的增大,算法执行时间的增长率和某个函数f(n)的增长率相同。换句话说,当问题规模n趋于无穷大时,算法运行时间的增长趋势的度量即为渐进时间复杂度。

为了分析一个算法的时间复杂度,通常需要考察算法中基本语句的执行次数,找出其与问题规模n的函数关系f(n)。基本语句是执行次数与算法的执行次数成正比的语句,它是算法中的关键操作。然后,用O(f(n))来表示算法的复杂度。这里,O表示大O表示法,用于描述算法执行时间的上界。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1006741.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Day30:安全开发-JS应用NodeJS指南原型链污染Express框架功能实现审计

目录 环境搭建-NodeJS-解析安装&库安装 功能实现-NodeJS-数据库&文件&执行 安全问题-NodeJS-注入&RCE&原型链 案例分析-NodeJS-CTF题目&源码审计 开发指南-NodeJS-安全SecGuide项目 思维导图 JS知识点&#xff1a; 功能&#xff1a;登录验证&…

《计算机网络》考研:2024/3/8 2.1.5-编码与调制(1)、2.1.6-编码与调制(2)

2024/3/8 2.1.5、2.1.6 编码与调制&#xff08;1&#xff09; 编码与调制&#xff08;2&#xff09; (据老师所解释&#xff0c;曼彻斯特编码在每个时钟周期内&#xff0c;开始时的信号也变换了一次&#xff0c;加上中间变换一次&#xff0c;因此每个周期内会变换两次。)

go切片实现原理

近日一直在学习golang,已经产出如下博客一篇 GO闭包实现原理(汇编级讲解) 引言 最近在使用go语言的切片时,出现了一些意料之外的情况,遂查询相关文档学习后写下此篇博客 正文 首先,我们思考,go在通过函数传递一个切片时,是通过引用传递的吗,还是通过值传递的呢(答案将会很…

pgsql常用索引简写

文章来源&#xff1a;互联网博客文章&#xff0c;后续有时间再来细化整理。 在数据库查询中&#xff0c;合理的使用索引&#xff0c;可以极大提升数据库查询效率&#xff0c;充分利用系统资源。这个随着数据量的增加得到提升&#xff0c;越大越明显&#xff0c;也和业务线有关…

进程等待详解

一、进程等待的作用 我们都知道&#xff0c;当子进程已经结束而父进程还在执行时&#xff0c;子进程会变成僵尸进程&#xff0c;造成内存泄漏等问题&#xff0c;如下&#xff1a; #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include &l…

2024/3/11打卡分巧克力(第8届蓝桥杯省赛)——二分

题目 儿童节那天有 K 位小朋友到小明家做客。 小明拿出了珍藏的巧克力招待小朋友们。 小明一共有 N 块巧克力&#xff0c;其中第 i 块是 HiWi 的方格组成的长方形。 为了公平起见&#xff0c;小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。 切出的巧克力需要满足&…

面试题:Redis 为什么读写性能高?

Redis 的速度⾮常快&#xff0c;单机的 Redis 就可以⽀撑每秒十几万的并发&#xff0c;性能是 MySQL 的⼏⼗倍。速度快的原因主要有⼏点&#xff1a; 基于内存的数据存储 Redis 将数据存储在内存当中&#xff0c;使得数据的读写操作避开了磁盘 I/O。而内存的访问速度远超硬盘&a…

数据处理分类、数据仓库产生原因

个人看书学习心得及日常复习思考记录&#xff0c;个人随笔。 数据处理分类 操作型数据处理&#xff08;基础&#xff09; 操作型数据处理主要完成数据的收集、整理、存储、查询和增删改操作等&#xff0c;主要由一般工作人员和基层管理人员完成。 联机事务处理系统&#xff…

opengl日记27-opengl报错ERROR::SHADER::PROGRAM::LINKING_FAILED

Author: wencoo Blog&#xff1a;https://wencoo.blog.csdn.net/ Date: 14/03/2024 Email: jianwen056aliyun.com Wechat&#xff1a;wencoo824 QQ&#xff1a;1419440391 Details:文章目录 目录正文 或 背景 报错信息ERROR::SHADER::PROGRAM::LINKING_FAILED解决方法情况1情况…

SpringController返回值和异常自动包装

今天遇到一个需求&#xff0c;在不改动原系统代码的情况下。将Controller的返回值和异常包装到一个统一的返回对象中去。 例如原系统的接口 public String myIp(ApiIgnore HttpServletRequest request);返回的只是一个IP字符串"0:0:0:0:0:0:0:1"&#xff0c;目前接口…

PandasAI—让AI做数据分析

安装 pip install pandasai !pip install --upgrade pandas pandasai 导入依赖项 import pandas as pdfrom pandasai import PandasAIfrom pandasai.llm.openai import OpenAI使用pandas创建一个数据框 df pd.DataFrame({"country": ["United States",…

如何解决ChatGPT消息发不出问题,GPT消息无法发出去,没有响应的问题

前言 今天工作到一半&#xff0c;登陆ChatGPT想咨询一些代码上的问题&#xff0c;结果发现发不了消息了。 ChatGPT 无法发送消息&#xff0c;但是能查看历史的对话。不过首先可以先打开官方的网站&#xff1a;https://status.openai.com/ 。 查看当前Open AI的状态&#xff0…

运放失调电压及其影响

运放失调电压及其影响 在运放的应用中&#xff0c;我们经常会遇到一个重要的性能指标——失调电压。本文将介绍失调电压的定义、优劣范围&#xff0c;并提供一些应对失调电压的方法。 定义 在运放开环使用时&#xff0c;加载在两个输入端之间的直流电压使得放大器直流输出电…

基于斑翠鸟优化算法(Pied Kingfisher Optimizer ,PKO)的无人机三维路径规划(MATLAB)

一、无人机路径规划模型介绍 二、算法介绍 斑翠鸟优化算法(Pied Kingfisher Optimizer ,PKO),是由Abdelazim Hussien于2024年提出的一种基于群体的新型元启发式算法,它从自然界中观察到的斑翠鸟独特的狩猎行为和共生关系中汲取灵感。PKO 算法围绕三个不同的阶段构建:栖息…

利用Java实现数据矩阵的可视化

1. 引言 在进行工程开发时&#xff0c;通常需要在窗口的某个区域将有效数据形象化地呈现出来&#xff0c;例如&#xff1a;对于某一区域的高程数据以伪色彩的方式呈现出高度的变化&#xff0c;这就需要解决利用Java进行数据呈现的问题。本文将建立新工程开始&#xff0c;逐步地…

VScode(Python)使用ssh远程开发(Linux系统树莓派)时,配置falke8和yapf总结避坑!最详细,一步到位!

写在前面&#xff1a;在Windows系统下使用VScode时可以很舒服的使用flake8和yapf&#xff0c;但是在ssh远程开发树莓派时&#xff0c;我却用不了&#xff0c;总是出现问题。当时我就开始了漫长的探索求知之路。中间也请教过许多大佬&#xff0c;但是他们就讲“能用不就行了&…

LabVIEW电磁阀特性测控系统

LabVIEW电磁阀特性测控系统 电磁阀作为自动化工程中的重要组成部分&#xff0c;其性能直接影响系统的稳定性和可靠性。设计一种基于LabVIEW的电磁阀特性测控系统&#xff0c;通过高精度数据采集和智能化控制技术&#xff0c;实现电磁阀流阻、响应时间及脉冲特性的准确测量和分…

【MySQL性能优化】- 一文了解MVCC机制

MySQL理解MVCC &#x1f604;生命不息&#xff0c;写作不止 &#x1f525; 继续踏上学习之路&#xff0c;学之分享笔记 &#x1f44a; 总有一天我也能像各位大佬一样 &#x1f3c6; 博客首页 怒放吧德德 To记录领地 &#x1f31d;分享学习心得&#xff0c;欢迎指正&#xff…

docker部署springboot jar包项目

docker部署springboot jar包项目 前提&#xff0c;服务器环境是docker环境&#xff0c;如果服务器没有安装docker&#xff0c;可以先安装docker环境。 各个环境安装docker&#xff1a; Ubuntu上安装Docker&#xff1a; ubuntu离线安装docker: CentOS7离线安装Docker&#xff1…

应急响应实战笔记03权限维持篇(6)

0x00 前言 在渗透测试中&#xff0c;有三个非常经典的渗透测试框架----Metasploit、Empire、Cobalt Strike。 那么&#xff0c;通过漏洞获取到目标主机权限后&#xff0c;如何利用框架获得持久性权限呢&#xff1f; 0x01 MSF权限维持 使用MSF维持权限的前提是先获得一个met…