当前位置: 首页 > 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; 【深圳】 入户 ①核准类入户:…...

Python对象生命周期管理失效了?——从引用计数到分代GC的隐性成本陷阱(附内存热力图诊断工具)

第一章&#xff1a;Python对象生命周期管理失效的典型现象与诊断范式Python 的自动内存管理依赖引用计数、循环垃圾收集器&#xff08;GC&#xff09;与弱引用机制协同工作&#xff0c;但当这些机制被意外绕过或干扰时&#xff0c;对象生命周期便可能失控。典型失效现象包括&am…...

经营分析会哪些指标最重要?老板最该看的10个经营分析指标

开经营分析会&#xff0c;最怕的就是数据。很多老板一开经营分析会就头疼&#xff1a;这么多数字&#xff0c;我到底该看哪个&#xff1f;做了十多年财务管理了&#xff0c;我一直在内部推行一套极简框架&#xff1a;所有经营讨论&#xff0c;都必须围绕这10个根本指标展开。这…...

面试:描述下bean的生命周期

1.实例化bean&#xff1a; 反射的方式生成对象 2.填充bean的属性&#xff1a; populateBean()&#xff0c;循环依赖的问题&#xff08;三级缓存&#xff09; 3.调用aware接口相关的方法&#xff1a; InvokeAwareMethod&#xff08;完成BeanName&#xff0c;BeanFactory&#xf…...

Magisk模块开发实战指南:从基础架构到高级功能实现

Magisk模块开发实战指南&#xff1a;从基础架构到高级功能实现 【免费下载链接】Magisk The Magic Mask for Android 项目地址: https://gitcode.com/GitHub_Trending/ma/Magisk Magisk模块开发是Android系统定制领域的核心技术&#xff0c;它通过独特的挂载机制让开发者…...

OpenClaw定时任务实战:Qwen3-4B驱动每日资讯摘要生成

OpenClaw定时任务实战&#xff1a;Qwen3-4B驱动每日资讯摘要生成 1. 为什么需要自动化资讯摘要 每天早上打开电脑&#xff0c;我的浏览器标签页总是堆满了十几个未读的科技资讯网站。作为技术从业者&#xff0c;保持行业敏感度很重要&#xff0c;但手动筛选和阅读的效率实在太…...

5分钟搞定!OpenCode+Qwen3-4B本地AI编程助手一键部署教程

5分钟搞定&#xff01;OpenCodeQwen3-4B本地AI编程助手一键部署教程 1. 引言&#xff1a;为什么你需要一个本地AI编程助手&#xff1f; 想象一下这个场景&#xff1a;你正在开发一个核心功能模块&#xff0c;需要快速生成一段复杂的业务逻辑代码。你打开浏览器&#xff0c;准…...

3个技巧让你轻松获取Steam创意工坊资源:WorkshopDL的跨平台下载解决方案

3个技巧让你轻松获取Steam创意工坊资源&#xff1a;WorkshopDL的跨平台下载解决方案 【免费下载链接】WorkshopDL WorkshopDL - The Best Steam Workshop Downloader 项目地址: https://gitcode.com/gh_mirrors/wo/WorkshopDL 在游戏模组爱好者的日常中&#xff0c;总会…...

用 DeepWiki 线索看 OpenClaw:它到底用到了哪些 AI 技术?

用 DeepWiki 线索看 OpenClaw&#xff1a;它到底用到了哪些 AI 技术&#xff1f; OpenClaw 近来在个人 AI 助手、Agent 框架和本地优先智能体领域里讨论度很高。很多人第一次看到它&#xff0c;会把它简单理解为“一个能接聊天渠道的大模型壳子”。但如果顺着 GitHub 文档以及项…...

Spring_couplet_generation 模型推理性能优化:操作系统级调优指南

Spring_couplet_generation 模型推理性能优化&#xff1a;操作系统级调优指南 想让你的春联生成模型跑得更快、更稳吗&#xff1f;很多朋友在部署AI模型时&#xff0c;往往只关注模型本身和代码&#xff0c;却忽略了承载这一切的“地基”——操作系统。今天&#xff0c;我们就…...

万象视界灵坛部署案例:阿里云ECS GPU实例一键拉起Omni-Vision Sanctuary服务

万象视界灵坛部署案例&#xff1a;阿里云ECS GPU实例一键拉起Omni-Vision Sanctuary服务 1. 项目概述 万象视界灵坛&#xff08;Omni-Vision Sanctuary&#xff09;是一款基于OpenAI CLIP技术的高级多模态智能感知平台。这个创新性的解决方案将复杂的视觉识别任务转化为直观、…...