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

【数据结构】空间复杂度

在这里插入图片描述

🚀write in front🚀
📜所属专栏:初阶数据结构
🛰️博客主页:睿睿的博客主页
🛰️代码仓库:🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!!
关注我,关注我,关注我你们将会看到更多的优质内容!!

在这里插入图片描述

文章目录

  • 前言:
  • 一.空间复杂度
    • 栗子1:
    • 栗子2:
    • 栗子3:
    • 栗子4:
  • 二.常见复杂度对比
  • 总结:

前言:

  上一篇博客我们讲解了时间复杂度的相关知识,那么时间有复杂度,可以有复杂度吗?下面我们就来了解一下空间复杂度的相关知识!

一.空间复杂度

 空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法。
注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间(变量个数)来确定

常数个变量的复杂度:O(n)

栗子1:

// 计算BubbleSort的空间复杂度?
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

空间复杂度为O(1)
因为调用了常数个常数个额外空间。

栗子2:

// 计算Fibonacci的空间复杂度?
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if (n == 0)return NULL;long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n; ++i){fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray;
}

空间复杂度为O(n)
动态开辟了n+1个空间

栗子3:

// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

空间复杂度为O(n)
递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。

栗子4:

// 计算斐波那契递归Fib的空间复杂度?
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

空间复杂度为O(N)
很多小伙伴可能会以为空间复杂度为O(2^N),但是实则不是。我们先来看看下面的图:
在这里插入图片描述
递归是有先后顺序,并不是同一时间内同时递归的,所以递归会按先后顺序依次递归,顺序就像如图所示的1 2 3 4 5 6……这样递归。所以开辟的空间最多为N个,随后返回空间。所以空间复杂度为O(N)。

二.常见复杂度对比

在这里插入图片描述

总结:

  这就是时间复杂度和空间复杂度的全部知识!希望对大家有所帮助
  更新不易,辛苦各位小伙伴们动动小手,👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要!最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!

专栏订阅:
每日一题
c语言学习
算法
智力题
初阶数据结构
更新不易,辛苦各位小伙伴们动动小手,👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要!最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!

在这里插入图片描述

相关文章:

【数据结构】空间复杂度

&#x1f680;write in front&#x1f680; &#x1f4dc;所属专栏&#xff1a;初阶数据结构 &#x1f6f0;️博客主页&#xff1a;睿睿的博客主页 &#x1f6f0;️代码仓库&#xff1a;&#x1f389;VS2022_C语言仓库 &#x1f3a1;您的点赞、关注、收藏、评论&#xff0c;是对…...

湖南中创教育提醒校外培训留意这几点,避免维权

校外教育培训机构是市场经济发展的必然产物&#xff0c;有需求就有市场&#xff0c;这个无可厚非。而校外教育培训机构的火热&#xff0c;正是反映出人民群众对教育发展的需求在不断增强。 培训机构分类中有面对大学生参加公务员招考、教师考编等考证考试的培训机构&#xff1…...

docker 配置私有/本地镜像仓库

docker 配置私有/本地镜像仓库docker pull registry mkdir -p /usr/local/docker/registry-data docker tag registry 192.168.28.132:5000/registry docker run -di -p 5000:5000 --namelocal_registry --restartalways --privilegedtrue --log-drivernone -v /usr/local/d…...

每日学术速递2.23

Subjects: Robotics 1.On discrete symmetries of robotics systems: A group-theoretic and data-driven analysis ​ 标题&#xff1a;关于机器人系统的离散对称性&#xff1a;群论和数据驱动分析 作者&#xff1a;Daniel Ordonez-Apraez, Mario Martin, Antonio Agudo, F…...

LeetCode 232. 用栈实现队列

LeetCode 232. 用栈实现队列 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作&#xff08;pushpushpush、poppoppop、peekpeekpeek、emptyemptyempty&#xff09;&#xff1a; 实现 MyQueueM…...

AI算法创新赛-人车目标检测竞赛总结04

队伍&#xff1a;AI000038 小组成员&#xff1a;杨志强&#xff0c;林松 1. 算法介绍 1.1 相关工作 当前流行的目标检测算法主要分为三种&#xff0c;一阶段算法&#xff1a;SSD&#xff0c;FCOS&#xff0c;Scaled&#xff0c;YOLO系列等&#xff1b;二阶段算法&#xff1a…...

【C语言进阶】动态内存管理详解与常见动态内存错误以及柔性数组使用与介绍

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;C语言进阶 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录1.动态内存1.1 概述…...

【C++】string的模拟实现

文章目录1. string的模拟实现1.构造函数使用new开辟空间优化成全缺省的构造函数2. C_str3. operator[]4.拷贝构造浅拷贝深拷贝5. 赋值三种情况6. 迭代器7.比较(ASCII值)大小8. reserve(扩容)9. push_back(尾插字符)10. append(尾插字符串)11. (字符/字符串)12. insert在pos位置…...

前端借助Canvas实现压缩base64图片两种方法

一、具体代码 1、利用canvas压缩图片方法一 // 第一种压缩图片方法&#xff08;图片base64,图片类型,压缩比例,回调函数&#xff09;// 图片类型是指 image/png、image/jpeg、image/webp(仅Chrome支持)// 该方法对以上三种图片类型都适用 压缩结果的图片base64与原类型相同// …...

用ChatGPT生成Excel公式,太方便了

ChatGPT 自去年 11 月 30 日 OpenAI 重磅推出以来&#xff0c;这款 AI 聊天机器人迅速成为 AI 界的「当红炸子鸡」。一经发布&#xff0c;不少网友更是痴迷到通宵熬夜和它对话聊天&#xff0c;就为了探究 ChatGPT 的应用天花板在哪里&#xff0c;经过试探不少人发现&#xff0c…...

【Kubernetes 企业项目实战】09、Rancher 2.6 管理 k8s-v1.23 及以上版本高可用集群

目录 一、Rancher 介绍 1.1Rancher简介 1.2 Rancher 和 k8s 的区别 1.3 Rancher 企业使用案例 二、安装 Rancher 2.1 初始化环境 2.2 安装 Rancher 2.3 登录 Rancher 平台 三、通过 Rancher 管理已存在的 k8s 集群 3.1 配置 rancher 3.2 导入 k8s ​四、通过 Ranc…...

在Excel中按条件筛选数据并存入新的表

案例 老板想要看去年每月领料数量大于1000的数据。手动筛选并复制粘贴出来,需要重复操作12次,实在太麻烦了,还是让Python来做吧。磨刀不误砍柴工,先整理一下思路: 1读取原表,将数量大于1000的数据所对应的行整行提取(如同在excel表中按数字筛选大于1000的) 2将提取的数…...

【面试题】MySQL索引相关知识点

1.什么是索引 索引是存储引擎快速查找记录的一种数据结构&#xff0c;就类似书的目录&#xff0c;通过目录可以快速的查找到想要查找的内容 2.索引的特点 特点&#xff1a;索引是基于数据引擎的&#xff0c;不同的数据引擎实现索引的方式不一定相同 好处&#xff1a;通过索引…...

MySQL索引类型及原理?一文读懂

一、什么是MySQL索引&#xff1f; MySQL索引是一种数据结构&#xff0c;用于提高数据库查询的性能。它类似于一本书的目录&#xff0c;通过在表中存储指向数据行的引用&#xff0c;使得查询数据的速度更快。 在MySQL中&#xff0c;索引通常是在表上定义的&#xff0c;它们可以…...

【C语言】字符分类函数+内存函数

目录 1.字符函数 1.1字符分类函数 1.2.字符转换函数 //统一字符串中的大小写 2.内存处理函数 2.1内存拷贝函数memcpy //模拟实现memcpy 2.2内存移动函数memmove //模拟实现memmove 2.3内存比较函数memcmp 2.4内存设置函数memset 1.字符函数 1.1字符分类函数 头文…...

高通平台开发系列讲解(SIM卡篇)SIM卡基础概念

文章目录 一、SIM卡基本定义二、卡的类型三、SIM卡的作用三、SIM卡基本硬件结构四、SIM卡的内部物理单元五、卡文件系统沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇文章将介绍SIM的相关组件。 一、SIM卡基本定义 SIM卡是一种智能卡(ICC Card/UICC Card) SIM…...

记录一次ubuntu下配置ssh登录出现的问题

现象描述: 1. 配置完服务器端公钥和本地的私钥之后&#xff0c;ssh登录始终会让输入密码&#xff0c;用ssh -vvv rootip 查看发现发送密钥之后就没反应了。 本机debug info: debug1: Trying private key: C:\Users\wangc/.ssh/id_xxxx &#xff08;私钥文件&#xff09; debug3…...

深度剖析数据在内存中的存储(下)(适合初学者)

上篇讲解了整形在内存中的存储方式&#xff0c;这篇文章就来继续讲解浮点数在内存中的存储方式。 上篇地址&#xff1a; (5条消息) 深度剖析数据在内存中的存储&#xff08;上&#xff09;_陈大大陈的博客-CSDN博客 目录&#xff1a; 3.浮点型在内存中的存储 3.1.浮点数的…...

智慧物联网系统源码:一个用于数据的收集、处理、可视化、设备管理、设备预警、报警的平台

项目简介&#xff1a; 一个用于数据的收集、处理、可视化、设备管理、设备预警、报警的平台&#xff0c;通过平台将所有设备连接起来&#xff0c;为上层应用提供设备的管理、数据收集、远程控制等核心物联网功能。 支持支持远程对设备进行实时监控、故障排查、远程控制&#…...

2023年,拥有软考证书在这些地区可以领取福利补贴

众所周知&#xff0c;软考的含金量很高&#xff0c;比如可以入户、领取技能补贴、抵扣个税、以考代评、招投标加分&#xff0c;入专家库… 今天小编给大家收集了拥有软考证书可以领取软考福利的地区&#xff0c;希望对大家有所帮助&#xff01; 【深圳】 入户 ①核准类入户:…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...