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

暑期数据结构 空间复杂度

3.空间复杂度
空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度。
空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。


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

我们直接上例题来讲解

void lystyle(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;}
}

首先我们要思考一下void lystyle(int*a;int n)这个函数声明中创建的a和n算不算到空间复杂度里面去,显然是不用的

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。(计算的是函数额外创建的变量个数)

这整个函数里面一共创建了三个变量分别是exchange,i,n占用的内存是不同的

因此创建变量是常数个,O(1)这个地方不知道为啥是O(1)可以看上一期的暑期数据结构 时间复杂度-CSDN博客

我们接下来看一个很有意思的事

但是为啥会导致这样呢?

原因在于我们使用函数时会开辟一片空间,函数结束时会将那片空间还给系统 ,但是下次另一个函数使用时开辟的那个空间还是原来函数的

那么还是上一期的函数(时间复杂度我会放到每日一题以一个数学专业的学生去讲解)

long long Fib(int N)
{if (N <= 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

那么这个地方的空间复杂度是多少呢?

有人可能说是O(0)但是只有函数本身声明中的变量才不算入空间复杂度里面,但是递归产生的变量会被算到时间复杂度里面

那么还有人可能说和时间复杂度一样是O(N*N),因为我每递归一次就执行了一次语句

但是结果也不对

那么答案是多少呢?

答案是O(N)

这个地方递归执行是有顺序的

这个地方return Fib(N - 1) + Fib(N - 2);

要先计算Fib(N - 1)再计算Fib(N - 2);

要计算Fib(N - 1)就要先算Fib(N - 2)+Fib(N -3 )

递归是一步一步实现的,不遇到return 不停止我们以N=6来画一个计算的过程图

这个地方我们看箭头4和5,我们先执行函数Fib(3)使用完之后函数空间还给系统,但是执行Fib(4)本质上再开辟的那个空间还是和Fib(3)一样的

因此这个地方同一深度的函数的是同一片空间(深度从上到下看)

因此这个地方的空间复杂度就是O(N)(我么只看最左侧看它最深度有多深就行)

相关文章:

暑期数据结构 空间复杂度

3&#xff0e;空间复杂度 空间复杂度也是一个数学表达式&#xff0c;是对一个算法在运行过程中临时占用存储空间大小的量度。 空间复杂度不是程序占用了多少bytes的空间&#xff0c;因为这个也没太大意义&#xff0c;所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟…...

【Android Studio】图标一键生成 Image Asset Studio(一键各机型适配图标生成工具-告别一个一个替换)

文章目录 方法一&#xff1a;原始替换方法二&#xff1a;Image Asset Studio 方法一&#xff1a;原始替换 https://blog.csdn.net/xzzteach/article/details/140821856 方法二&#xff1a;Image Asset Studio 自动替换所有机型图标...

C++ | Leetcode C++题解之第332题重新安排行程

题目&#xff1a; 题解&#xff1a; class Solution { public:unordered_map<string, priority_queue<string, vector<string>, std::greater<string>>> vec;vector<string> stk;void dfs(const string& curr) {while (vec.count(curr) &am…...

使用Python实现简单的网页爬虫:抓取网站标题

使用Python实现简单的网页爬虫:抓取网站标题 在当今数据驱动的时代,网络爬虫(Web Crawler)成为了获取和分析网络数据的重要工具。无论是数据科学、市场分析还是学术研究,爬虫都能帮助我们从互联网上提取有价值的信息。本文将介绍如何使用Python实现一个简单的爬虫,抓取某…...

视觉SLAM ch3—三维空间的刚体运动

如果对于某些线性代数的知识不太牢固&#xff0c;可以看一下我的另一篇博客&#xff0c;写了一些基础知识并推荐了一些视频。 旋转矩阵 单元所需的线代基础知识https://blog.csdn.net/Johaden/article/details/141023668 一、旋转矩阵 1.点、向量、坐标系 在数学中&…...

计算机毕业设计选题推荐-二手图书交易系统-Java/Python项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…...

4.MySQL数据类型

目录 数据类型 ​编辑数值类型 tinyint类型 bit类型 float类型 decimal类型 字符串类型 char类型 varchar varchar和char的区别 日期和时间类型 数据类型 数值类型 说明一下&#xff1a;MySQL本身是不支持bool类型的&#xff0c;当把一个数据设置成bool类型时&#x…...

快递查询新纪元:一键批量获取多家快递物流详情

跨快递平台批量查询神器&#xff1a;一站式解决信息追踪难题——固乔快递查询助手 在电商行业日益繁荣的今天&#xff0c;快递服务已经成为连接买卖双方不可或缺的一环。然而&#xff0c;随着合作的快递公司日益增多&#xff0c;如何高效地管理和追踪不同平台的快递信息&#…...

docker部署redis和mongoDB

docker部署mongoDB redismongoDB redis # --requirepass指定redis连接时的密码 # --appendonly yes 开启reids的AOF功能 docker run --name redis -p 6379:6379 -d redis:5.0.14 redis-server --requirepass 1234 --appendonly yes# 以/etc/redis/redis.conf的配置信息启动red…...

了解LVS,配置LVS

项目一、LVS 1.集群Cluster Cluster: 集群是为了解决某个特定问题将堕胎计算机组合起来形成的单个系统 LB&#xff1a;负载均衡 HA&#xff1a;高可用 HPC&#xff1a;高性能计算 2.分布式 分布式是将一个请求分成三个部分&#xff0c;按照功能拆分&#xff0c;使用微服…...

目标检测综述文章解读——Object Detection in 20 Years: A Survey

论文&#xff1a;Object Detection in 20 Years: A Survey 作者&#xff1a;Zhengxia Zou, Keyan Chen, Zhenwei Shi, Yuhong Guo, Jieping Ye 链接&#xff1a;https://arxiv.org/abs/1905.05055 这是一篇关于目标检测综述性文章&#xff0c;自2019年5月第一次提交后&#xff…...

Android make_vbmeta_image的参数值定义

网上生成vbmeta_system.img的命令,分析下这些参数的赋值,key的路径 out/host/linux-x86/bin/avbtool make_vbmeta_image --algorithm SHA256_RSA2048 --key device/mediatek/system/common/key/rsa2048/oem_prvk.pem --padding_size 4096 --rollback_index 0 --...

代码规范 —— 并发编程规范

优质博文&#xff1a;IT-BLOG-CN 【1】【强制】获取单例对象需要保证线程安全&#xff0c;其中的方法也要保证线程安全。 说明&#xff1a; 资源驱动类、工具类、单例工厂类都需要注意。 【2】【强制】创建线程或线程池时请指定有意义的线程名称&#xff0c;方便出错时回溯。…...

仪器仪表控制:pymeasure常用模块以及API

下面是对 pymeasure.experiment 模块中各类和方法的详细介绍&#xff0c;包括它们的功能和用法。 pymeasure.experiment 模块详细介绍 Experiment 类 Experiment 类是 Pymeasure 中用于定义和管理实验的核心类。它包含实验的设置、执行和数据记录等功能。 构造函数 class …...

如何理解openfoam案例里面的blockMesh文件里面的simpleGrading

总结&#xff1a; simpleGrading参数分为xyz三个方向。如果你想使得网格在某个方向上更密集&#xff0c;可以在simpleGrading中将该方向的渐变率设置为小于 1 .更稀疏则设置大于1. 一、案例 比如我这个爆炸案例&#xff1a; 对应的blockMeshDIct文件如下&#xff1a; // 定…...

算法竞赛的制胜法宝:被严重低估的位运算究竟有什么用?

大家好&#xff0c;我是干货哥。今天咱们来聊聊一个让很多人都忽略的神技——位运算。等等&#xff0c;你是不是已经准备关掉这篇文章了&#xff1f;你以为位运算只是计算机底层的鸡肋操作&#xff1f;你以为这些不过是编程语言里最基础、最无趣的东西&#xff1f;但真的是这样…...

Qt QTableWidget 去除序号列

ui->tableWidget->verticalHeader()->setHidden(true);//垂直序列号&#xff08;表左侧&#xff09;ui.tableWidget->horizontalHeader()->setHidden(true);//水平序列号&#xff08;表上方&#xff09;删除后效果图&#xff1a;...

【C++】5.类和对象(3)

文章目录 3.析构函数析构函数的特点&#xff1a; 4.拷贝构造函数拷贝构造的特点&#xff1a; 3.析构函数 析构函数与构造函数功能相反&#xff0c;析构函数不是完成对对象本身的销毁&#xff0c;比如局部对象是存在栈帧的&#xff0c;函数结束栈帧销毁&#xff0c;他就释放了&…...

CTF-RCE

eval执行 ?cmdsystemctl("ls"); ?cmdsystemctl("ls /"); ?cmdsystemctl("cat /flag_27523); 命令注入 输入ip试试发先可以执行 127.0.0.1 查看一下看看有社么 127.0.0.1 | ls 试着看看php文件 127.0.0.1 | cat 297581345892.php 貌似这个文件有…...

谷歌账号登录时,多次验证后变成“您的计算机或网络可能在发送自动查询内容”,原因分析和解决建议

最近有多个朋友联系GG账号服务&#xff0c;反馈说谷歌账号登录的时候&#xff0c;提示谷歌账号活动异常&#xff0c;需要输入手机号验证&#xff0c;但是自己的手机号无法验证&#xff0c;要不提示无法用于进行验证&#xff0c;要不提示用于验证的次数过多。 有一些朋友第一次遇…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

反射获取方法和属性

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

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》

&#x1f9e0; LangChain 中 TextSplitter 的使用详解&#xff1a;从基础到进阶&#xff08;附代码&#xff09; 一、前言 在处理大规模文本数据时&#xff0c;特别是在构建知识库或进行大模型训练与推理时&#xff0c;文本切分&#xff08;Text Splitting&#xff09; 是一个…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁

赛门铁克威胁猎手团队最新报告披露&#xff0c;数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据&#xff0c;严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能&#xff0c;但SEMR…...