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

数据结构-算法的空间复杂度(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 空间的特殊性质 写在最后&#xff1a; 1.空间复杂度 空间复杂度也是一个数学表达式&#xff0c; 是对一个算法在运行过程中临时占用存储空间大小的量度。 他也是用大O渐进表示法。 1.1 例子 例1&#xff1a; 冒泡排序&#xff1a; v…...

【总结】python3启动web服务引发的一系列问题

背景 在某行的实施项目&#xff0c;需要使用python3环境运行某些py脚本。 由于行内交付的机器已自带python3 &#xff0c;没有采取自行安装python3&#xff0c;但是运行python脚本时报没有tornado module。 错误信息 ModuleNotFoundError&#xff1a;No module named ‘torn…...

Linux:基于libevent读写管道代码,改进一下上一篇变成可以接收键盘输入

对上一篇进行改进&#xff0c;变成可以接收键盘输入&#xff0c;然后写入管道&#xff1a; 读端代码&#xff1a; #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函数

凡事发生必将有益于我&#xff0c;高手&#xff0c;从来都不仅仅是具备某种思维的人&#xff0c;而是那些具备良好学习习惯的人&#xff0c;成为高手&#xff0c;无他&#xff0c;手熟尔&#xff01;加油在最近的学习之中&#xff0c;对于格式化输出这个知识点&#xff0c;这里…...

Nginx之反向代理、负载均衡、动静分离。

Nginx之反向代理、负载均衡、动静分离。 1、Nginx是啥&#xff1f; 轻量级Web服务器、反向代理服务器、电子邮件&#xff08;IMAP/POP3&#xff09;代理服务器 在 BSD-like 协议下发行、占内存少、并发高&#xff08;同时处理请求能力&#xff09;。 2、安装 官网&#xf…...

0401不定积分的概念和性质-不定积分

文章目录1 原函数与不定积分的概念1.1 原函数1.2 原函数存在定理1.3 不定积分2 不定积分的性质3 基本积分表4 例题后记1 原函数与不定积分的概念 1.1 原函数 定义1 如果在区间I上&#xff0c;可导函数F(x)的导航为f(x)&#xff0c;即对任一x∈Ix\in Ix∈I&#xff0c;都有 F′…...

数组中的各种迭代API方法手写

js的数组上有很多实用的方法&#xff0c;不论是在遍历数组上&#xff0c;还是在操作数组内元素上&#xff0c;它有许多不同的遍历数组的方法&#xff0c;同时它还有着可以直接操作数组中间元素的方法。 接下来&#xff0c;我来带大家手写数组里的 遍历方法 。 Array.forEach(…...

详解量子计算:相位反冲与相位反转

前言 本文需要对量子计算有一定的了解。需要的请翻阅我的量子专栏&#xff0c;这里不再涉及基础知识的科普。 量子相位反冲是什么&#xff1f; 相位反转&#xff08;phase kickback&#xff09;是量子计算中的一种现象&#xff0c;通常在量子算法中使用&#xff0c;例如量子…...

C++——C++11第三篇

目录 包装器 function包装器 bind 包装器 function包装器 function包装器 也叫作适配器。C中的function本质是一个类模板&#xff0c;也是一个包装器。 上面的程序验证&#xff0c;我们会发现useF函数模板实例化了三份。 包装器可以很好的解决上面的问题 &#xff0c;让它只实…...

180 2 22222

选择题(共180题,合计180.0分) 1. 在项目开工会议期间&#xff0c;项目发起人告诉产品负责人和团队项目章程即将完成。然而&#xff0c;由于存在在紧迫的期限内满足政府监管要求的压力&#xff0c;发起人希望立即开始工作。产品负责人下一步应该做什么&#xff1f; A 告诉发起人…...

成人高考初中毕业能报名吗 需要什么条件

初中学历的人员不能直接报名成人高考&#xff0c;考生需要有普通高中&#xff0c;职业高中&#xff0c;中专毕业证等高中同等学力就可以进行报名&#xff0c;在报名期间登陆所在省的教育考试院的成人高考报名入口进行报考。成人高考报名条件是什么1、遵守宪法和法律。2、国家承…...

ChatGPT初体验

ChatGPT初体验 前言 嘿嘿&#xff0c;最近啊AI ChatGPT刷新各大网站&#xff0c;对于我们国人而将很不友好&#xff0c;真的太不友好了。我呢在去年open AI发布的时候就有所关注&#xff0c;那个时候还没有像现在这样火热。谁知道短短几个月便传遍大街小巷。 一、什么是chatG…...

ChatGPT概念狂飙!究竟魅力何在?

原文&#xff1a;http://www.btcwbo.com/6988.html 近期&#xff0c;ChatGPT引领的人工智能概念在资本市场一路狂飙&#xff0c;AIGC题材持续发酵。截至2月7日&#xff0c;Wind ChatGPT指数今年以来累计上涨超50%&#xff0c;汉王科技、海天瑞声、云从科技等概念股股价已经翻倍…...

如何下载阅读Spring源码-全过程详解

这篇文章记录了下载spring源码和在IDEA中打开运行的全过程&#xff0c;并且记录了过程中遇到的问题和解决方案&#xff0c;适合需要学习spring源码的同学阅读。 1.spring源码下载地址 通过Git下载spring-framework项目源码&#xff1a; git clone https://github.com/spring…...

学了两个月的Java,最后自己什么也不会,该怎么办?

学着学着你会发现每天的知识都在更新&#xff0c;也都在遗忘&#xff0c;可能就放弃了。但是只要自己肯练&#xff0c;肯敲代码&#xff0c;学过的知识是很容易就被捡起来的。等你学透了用不了一年也可以学好 Java的运行原理&#xff1a;Java是一门编译解释型语言&#xff0c;…...

前端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目录&#xff0c;并解压 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 修改为如下&#xff1a; dataDir/data/zooke…...

单片机输入输出模式

单片机输入输出模式输入模式模拟输入、浮空输入、上拉输入、下拉输入GPIO输出模式推挽输出、开漏输出、复用推挽输出、复用开漏输出。上下拉电阻上拉电阻下拉电阻输入模式 模拟输入、浮空输入、上拉输入、下拉输入 模拟输入&#xff1a;I/O端口的模拟信号&#xff08;电压信号…...

数据结构_ 堆结构与堆排序(c++ 实现 + 完整代码 )

堆结构与堆排序 文章目录堆结构与堆排序引入堆堆结构所满足的数学特性准备代码----------- 往堆中插入元素----------- 删除堆顶堆排序构建完整代码及测试动态分配版本非动态版本引入堆 二叉树 具有左孩子与右孩子的最普通的二叉树。 满二叉树 特殊的二叉树&#xff1a;每个节…...

【MySQL】sql中explain解释和应用

这里写目录标题学习原因MySQL中explain的使用和用法解释explain的使用explain 运行结果的意义文字展示表格展示参考资料&#xff1a;结束语学习原因 在对sql的优化过程中使用了explain对指定的sql进行查看它的运行效果&#xff0c;以便找出sql的性能特点并进行优化 MySQL中ex…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

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;用于图像分割或平滑处理。 该函数将输入图像中的…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...