时间复杂度与空间复杂度的计算

空间复杂度 (O(1))

空间复杂度是衡量算法在运行过程中所需的额外内存空间。(O(1)) 表示算法只需要常量级别的额外空间,不会随着输入数据的大小 (n) 增加而增加。也就是说,无论处理的数据有多大,算法所需的额外内存空间始终是固定的。

对于选择排序和冒泡排序来说,它们都是原地排序算法,不需要额外的数组或其他数据结构来辅助排序操作。它们仅仅需要少量的临时变量(例如用于交换元素的变量),所以它们的空间复杂度是 (O(1))。

时间复杂度 (O(n^2))

时间复杂度是衡量算法执行所需的时间随输入数据规模 (n) 增加而增加的速率。(O(n^2)) 表示算法的运行时间与输入数据规模的平方成正比。当数据量增加时,执行时间会以平方的速度增加。

选择排序的时间复杂度

选择排序在每一轮中都要从未排序的部分中找到最小的元素,然后将其放到已排序部分的末尾。对于长度为 (n) 的数组,选择排序的操作步骤如下:

  1. 第一轮:需要比较 (n) 个元素,找到最小的。
  2. 第二轮:需要比较剩下的 (n-1) 个元素,找到次小的。
  3. 第三轮:需要比较剩下的 (n-2) 个元素,依此类推。

总比较次数为:

在这里插入图片描述

因此,时间复杂度为 (O(n^2))。

冒泡排序的时间复杂度

冒泡排序在每一轮中都要通过相邻元素的比较和交换,将最大(或最小)的元素“冒泡”到数组的一端。对于长度为 (n) 的数组,冒泡排序的操作步骤如下:

  1. 第一轮:需要比较 (n-1) 对相邻元素。
  2. 第二轮:需要比较剩下的 (n-2) 对相邻元素。
  3. 第三轮:需要比较剩下的 (n-3) 对相邻元素,依此类推。

总比较次数为:
在这里插入图片描述

因此,时间复杂度为 (O(n^2))。

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

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

相关文章

链表的回文结构的判定(C语言)怎会如此简单!!!

目录 题目思路分析如何找到中间节点如何实现反转链表链表的对比完整代码 题目 链接: 题目 描述: 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 给定一个链表的头指针A,请返回一个…

php反序列化中的pop链

目录 一、什么是POP 二、成员属性赋值对象 例题: 方法一 方法二 三、魔术方法的触发规则 例题: 四、POC的编写 例题1: 例题2 [NISACTF 2022]babyserialize 今日总结: 一、什么是POP 在反序列化中,我们…

Git配置免密登录Github

1、登录 GitHub ,点击右上角头像,选中 Settings (设置)。 在 https://github.com 登录你的帐号,登录以后点击右上角你的头像的Settings 如果没有设置,输入下面的指令进行设置: git config --global user.name “用户名…

【启明智显技术分享】sigmastar ssd202d双网口开发板多串口调试说明

提示:作为Espressif(乐鑫科技)大中华区合作伙伴及sigmastar(厦门星宸)VAD合作伙伴,我们不仅用心整理了你在开发过程中可能会遇到的问题以及快速上手的简明教程供开发小伙伴参考。同时也用心整理了乐鑫及星宸…

cesium 的初步认识

Cesium是一个基于JavaScript开发的WebGL三维地球和地图可视化库。它利用了现代Web技术,如HTML5、WebGL和WebAssembly,来提供跨平台和跨浏览器的三维地理空间数据可视化。Cesium的主要特点包括: 跨平台、跨浏览器:无需额外插件&am…

4个免费音频转换器:解放您的音频文件格式转换需求

在日常生活和工作中,我们经常需要处理各种音频文件,但有时候这些文件可能并不是我们需要的特定格式。在这种情况下,一个免费的音频转换器就能派上用场。免费音频转换器是一种非常实用的工具,它可以帮助我们将不同格式的音频文件相…

C++栈、队列

文章目录 目录 文章目录 前言 一、stack、queue介绍 1.stack 2.queue 二、stack、queue的习题 1. 最小栈 2. 栈的压入、弹出序列 3.二叉树的层序遍历 三、stack和queue的模拟实现 1.stack的模拟实现 2.queue的模拟实现 前言 栈和队列是俩种特殊的容器,C在实现栈和队…

contentType 与 dataType

contentType 与 dataType contentType contentType:发送的数据格式(请求方发送给服务器的数据格式),这个内容会放在请求方的 请求头中 application/x-www-form-urlencoded 这个是默认的请求格式。 提交给后台的数据会按照 KV&am…

瑞意教育集团阳光助学 军训展风采 青春正当时2024级新生军训圆满落幕

为推进全民素质教育,弘扬爱国主义精神,增强学生的国防意识,培养顽强的意志品格,5月7日—5月10日,瑞意教育集团举行2024级新生军训活动。 2024年5月7日上午8点,瑞意教育集团2024级新生军训动员大会在学校体育场举行,学校校长郭禹彤出席动员大会,并强调注意事项。 "立正!&qu…

AIGC绘画基础——Midjourney关键词大全+万能公式

距发布MJ初级注册入门教程已有时日,很多粉丝表示很有用,但关键词有很多人不知如何组合使用,那今天再给大家更新一期,主要是教大家如何用关键词、把控关键词描述,除此之外在文末更新了一大堆关键词给大家使用~ 一、Midj…

算法工程师需要学习C++的哪些知识?

在开始前刚好我有一些资料,是我根据网友给的问题精心整理了一份「C的资料从专业入门到高级教程」, 点个关注在评论区回复“888”之后私信回复“888”,全部无偿共享给大家!!!以下是算法工程师需要学习的一些…

韶关学院携手泰迪智能科技“见习研学”活动圆满结束

为进一步深化校企合作,落实高校应用型人才培养。5月31日,韶关学院与广东泰迪智能科技股份有限公司联合开展学生企业见习活动。专业教师林思思以及来自韶关学院140名学生参与此次见习活动,泰迪智能科技培训业务部经理钟秋平、校企合作经理吴桂…

linux系统getopt_long函数使用

在linux程序中,我们还经常看见使用--标识输入参数的,这种就需要使用getopt_long函数来解析。 如下使用方式: while ((opt getopt_long(argc, argv, short_options, long_options, &option_index)) ! -1) { //...... } 参数longopts结…

【Python入门学习笔记】Python3超详细的入门学习笔记,非常详细(适合小白入门学习)

Python3基础 想要获取pdf或markdown格式的笔记文件点击以下链接获取 Python入门学习笔记点击我获取 1,Python3 基础语法 1-1 编码 默认情况下,Python 3 源码文件以 UTF-8 编码,所有字符串都是 unicode 字符串。 当然你也可以为源码文件指…

VSCode编译C++代码

1. 自定义编译 主要通过 设置任务(动作)来实现。 tasks.json文件相当于vscode的.sh或.bat文件,用来记录一系列操作的宏。 一系列动作,那就可以用来设置 如何编译文件,如何 运行文件,几乎.sh能干的都可以干…

三维地图校内导航系统解决方案

在如今的数字化时代,越来越多的学校开始实施智慧校园计划,旨在为学生和教师提供更高效、便捷的学习和教学环境。智慧校园运用互联网、大数据、人工智能等技术,对校园内各信息进行收集、整合、分析和应用,实现教学、管理、服务等多…

python-旋转字符串

问题描述:给定一个字符串(以字符串数组的形式)和一个偏移量,根据偏移量从左到右地旋转字符数组。 问题示例:输入str”abcdefg”,offset3,输出“efgabcd”。输入str”abcdefg”,offset0,输出“abcdefg”。(返…

深度解析:速卖通618风控下自养号测评的技术要点

速卖通每年的618大促活动平台的风控都会做升级,那相对的测评技术也需要进行相应的做升级,速卖通618风控升级后,自养号测评需要注意以下技术问题,以确保测评 的稳定性和安全性: 一、物理环境 1. 硬件参数伪装&#x…

Linux 36.3 + JetPack v6.0@jetson-inference之目标检测

Linux 36.3 JetPack v6.0jetson-inference之目标检测 1. 源由2. detectnet2.1 命令选项2.2 下载模型2.3 操作示例2.3.1 单张照片2.3.2 多张照片2.3.3 视频 3. 代码3.1 Python3.2 C 4. 参考资料 1. 源由 从应用角度来说,目标检测是计算机视觉里面第二个重要环节。之…

商家转账到零钱功能千次开通操作分享

小程序地理位置接口有什么功能? 通常在申请开通getLocation 接口被驳回,驳回理由“申请的接口因提供的申请原因/辅助图片/网页/视频内容/无法确认申请接口使用场景”。原因是没有准确提供在那个场景调取地图定位功能,可以按以下步骤提供使用地…