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

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...