数据结构-算法的空间复杂度(1.2)
目录
1.空间复杂度
1.1 例子
1.2 空间的特殊性质
写在最后:
1.空间复杂度
空间复杂度也是一个数学表达式,
是对一个算法在运行过程中临时占用存储空间大小的量度。
他也是用大O渐进表示法。
1.1 例子
例1:
冒泡排序:
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:
斐波那契数列:
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;
}
这里用malloc开辟了n个以上的空间,
所以它的空间复杂度是O(N)。
例3:
阶乘递归:
long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}
这段代码,
因为函数递归,建立函数栈帧,
而函数栈帧里有常数个(空间)变量开辟,
而这段代码,建立了N+1个函数栈帧,
所以它的空间复杂度是O(N)。
1.2 空间的特殊性质
例4:
long long Fib(int N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}
这段代码的时间复杂度是O(2的N次方)。
但是,它的空间复杂度呢?
实际上,他的空间复杂度是O(N),而不是O(2的N次方)。
为什么呢?
因为函数递归的过程中会建立栈帧,而这段代码在进行递归的时候,
并不会一直递归到最后才返回,
当它递归到一定程度是,会有函数提前返回,
导致栈帧销毁,当新的栈帧建立的时候,
空间就会被重复使用,
例:
#include <stdio.h>void f1()
{int b = 0;printf("%p\n", &b);
}void f2()
{int a = 0;printf("%p\n", &a);
}int main()
{f1();f2();return 0;
}
输出:

我们发现,当f1函数的栈帧销毁后,
f2函数栈帧建立,创建的变量地址与f1中创建的变量地址相同,
这就是空间重复利用的特性。
例:
#include <stdio.h>void f1()
{int b = 0;printf("%p\n", &b);
}void f2()
{int a = 0;printf("%p\n", &a);f1();
}int main()
{f2();return 0;
}
输出:

当f1函数的栈帧没有销毁,
f2函数的变量自然用不了f1函数的空间,
所以他们的地址当然不同了。
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果喜欢本文的话,欢迎点赞和评论,写下你的见解。
如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。
之后我还会输出更多高质量内容,欢迎收看。
相关文章:
数据结构-算法的空间复杂度(1.2)
目录 1.空间复杂度 1.1 例子 1.2 空间的特殊性质 写在最后: 1.空间复杂度 空间复杂度也是一个数学表达式, 是对一个算法在运行过程中临时占用存储空间大小的量度。 他也是用大O渐进表示法。 1.1 例子 例1: 冒泡排序: v…...
【总结】python3启动web服务引发的一系列问题
背景 在某行的实施项目,需要使用python3环境运行某些py脚本。 由于行内交付的机器已自带python3 ,没有采取自行安装python3,但是运行python脚本时报没有tornado module。 错误信息 ModuleNotFoundError:No module named ‘torn…...
Linux:基于libevent读写管道代码,改进一下上一篇变成可以接收键盘输入
对上一篇进行改进,变成可以接收键盘输入,然后写入管道: 读端代码: #include <stdlib.h> #include <stdio.h> #include <unistd.h> #include <sys/types.h> #include <sys/stat.h> #include <s…...
C语言格式化输出总结:%d,%c,%s,%f, %lf,%m.nd,%m.nf,%m.ns 以及sprintf函数
凡事发生必将有益于我,高手,从来都不仅仅是具备某种思维的人,而是那些具备良好学习习惯的人,成为高手,无他,手熟尔!加油在最近的学习之中,对于格式化输出这个知识点,这里…...
Nginx之反向代理、负载均衡、动静分离。
Nginx之反向代理、负载均衡、动静分离。 1、Nginx是啥? 轻量级Web服务器、反向代理服务器、电子邮件(IMAP/POP3)代理服务器 在 BSD-like 协议下发行、占内存少、并发高(同时处理请求能力)。 2、安装 官网…...
0401不定积分的概念和性质-不定积分
文章目录1 原函数与不定积分的概念1.1 原函数1.2 原函数存在定理1.3 不定积分2 不定积分的性质3 基本积分表4 例题后记1 原函数与不定积分的概念 1.1 原函数 定义1 如果在区间I上,可导函数F(x)的导航为f(x),即对任一x∈Ix\in Ix∈I,都有 F′…...
数组中的各种迭代API方法手写
js的数组上有很多实用的方法,不论是在遍历数组上,还是在操作数组内元素上,它有许多不同的遍历数组的方法,同时它还有着可以直接操作数组中间元素的方法。 接下来,我来带大家手写数组里的 遍历方法 。 Array.forEach(…...
详解量子计算:相位反冲与相位反转
前言 本文需要对量子计算有一定的了解。需要的请翻阅我的量子专栏,这里不再涉及基础知识的科普。 量子相位反冲是什么? 相位反转(phase kickback)是量子计算中的一种现象,通常在量子算法中使用,例如量子…...
C++——C++11第三篇
目录 包装器 function包装器 bind 包装器 function包装器 function包装器 也叫作适配器。C中的function本质是一个类模板,也是一个包装器。 上面的程序验证,我们会发现useF函数模板实例化了三份。 包装器可以很好的解决上面的问题 ,让它只实…...
180 2 22222
选择题(共180题,合计180.0分) 1. 在项目开工会议期间,项目发起人告诉产品负责人和团队项目章程即将完成。然而,由于存在在紧迫的期限内满足政府监管要求的压力,发起人希望立即开始工作。产品负责人下一步应该做什么? A 告诉发起人…...
成人高考初中毕业能报名吗 需要什么条件
初中学历的人员不能直接报名成人高考,考生需要有普通高中,职业高中,中专毕业证等高中同等学力就可以进行报名,在报名期间登陆所在省的教育考试院的成人高考报名入口进行报考。成人高考报名条件是什么1、遵守宪法和法律。2、国家承…...
ChatGPT初体验
ChatGPT初体验 前言 嘿嘿,最近啊AI ChatGPT刷新各大网站,对于我们国人而将很不友好,真的太不友好了。我呢在去年open AI发布的时候就有所关注,那个时候还没有像现在这样火热。谁知道短短几个月便传遍大街小巷。 一、什么是chatG…...
ChatGPT概念狂飙!究竟魅力何在?
原文:http://www.btcwbo.com/6988.html 近期,ChatGPT引领的人工智能概念在资本市场一路狂飙,AIGC题材持续发酵。截至2月7日,Wind ChatGPT指数今年以来累计上涨超50%,汉王科技、海天瑞声、云从科技等概念股股价已经翻倍…...
如何下载阅读Spring源码-全过程详解
这篇文章记录了下载spring源码和在IDEA中打开运行的全过程,并且记录了过程中遇到的问题和解决方案,适合需要学习spring源码的同学阅读。 1.spring源码下载地址 通过Git下载spring-framework项目源码: git clone https://github.com/spring…...
学了两个月的Java,最后自己什么也不会,该怎么办?
学着学着你会发现每天的知识都在更新,也都在遗忘,可能就放弃了。但是只要自己肯练,肯敲代码,学过的知识是很容易就被捡起来的。等你学透了用不了一年也可以学好 Java的运行原理:Java是一门编译解释型语言,…...
前端vue实现获取七天时间和星期几功能
前端vue实现获取七天时间和星期几功能 功能展示代码 <div v-for"(item,index) in same_week" :class"[same_dayitem.date? activ :,dis]" click"select(item)" :keyindex><span>{{item.name}}</span><span>{{item.…...
zookeeper单机部署
一.下载zookeeper压缩包 二.上传解压安装包到/data/zookeeper目录,并解压 tar -zxvf apache-zookeeper-3.5.8-bin.tar.gz 三.修改配置文件 cd apache-zookeeper-3.5.10-bin/conf mv zoo_sample.cfg zoo.cfg vi zoo.cfg 修改为如下: dataDir/data/zooke…...
单片机输入输出模式
单片机输入输出模式输入模式模拟输入、浮空输入、上拉输入、下拉输入GPIO输出模式推挽输出、开漏输出、复用推挽输出、复用开漏输出。上下拉电阻上拉电阻下拉电阻输入模式 模拟输入、浮空输入、上拉输入、下拉输入 模拟输入:I/O端口的模拟信号(电压信号…...
数据结构_ 堆结构与堆排序(c++ 实现 + 完整代码 )
堆结构与堆排序 文章目录堆结构与堆排序引入堆堆结构所满足的数学特性准备代码----------- 往堆中插入元素----------- 删除堆顶堆排序构建完整代码及测试动态分配版本非动态版本引入堆 二叉树 具有左孩子与右孩子的最普通的二叉树。 满二叉树 特殊的二叉树:每个节…...
【MySQL】sql中explain解释和应用
这里写目录标题学习原因MySQL中explain的使用和用法解释explain的使用explain 运行结果的意义文字展示表格展示参考资料:结束语学习原因 在对sql的优化过程中使用了explain对指定的sql进行查看它的运行效果,以便找出sql的性能特点并进行优化 MySQL中ex…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...
