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

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

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

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

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...