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

【研究空间复用及函数调用问题】

本篇总结函数调用过程会存在的一些奇怪现象,空间复用问题,其实本质上涉及函数调用的底层原理,理解函数栈帧的创建和销毁这样的问题直接迎刃而解。

  • 1.空间复用问题
    • 案例1
    • 案例2
  • 2.函数调用过程不清晰问题
    • 案例3
  • 3.总结

1.空间复用问题

案例1

我们先来看一个代码:

void F1()
{int a = 10;printf("%p\n", &a);
}
void F2()
{int b = 10;printf("%p\n", &b);
}
int main()
{F1();F2();return 0;
}

F1和F2函数的操作基本一样,你说它们所开辟的空间的地址是同一块吗?
或者说,a和b的地址是一样的吗?

结果是:一样的。为什么呢?

在这里插入图片描述
我们知道调用函数需要给函数开辟栈帧,也就是开辟空间,而栈帧是在堆区开辟的
当函数使用完后,该函数栈帧就要销毁。

但不是真正意义上的销毁,而是把使用该空间的权限还给操作系统,这片区域不再受你操控。

所以我们在调用F1()函数时,操作系统先给F1()开辟栈帧,给变量a分配内存。然后当F1()函数结束时,该空间又被操作系统收回
接着又调用F2()函数,操作系统又将刚刚收回的空间又分配给F2()函数。
所以F1函数和F2函数使用的空间地址是一样的,变量a和变量b的地址也就是一样的。

在这里插入图片描述

案例2

这是一个阶乘递归的代码

long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}
int main()
{long long n;Fac(n);return 0;
}

请问它的空间复杂度和时间复杂度是多少呢?

函数Fac每次调用都会返回Fac(n-1)*n,直到N==0时才返回1.
也就是递归了n次,所以时间复杂度为O(n).
而空间复杂度呢?
因为Fac函数每次调用自己都会开辟一个函数栈帧,调用了n次,所以开辟了n个空间。
所以空间复杂度也是O(n).
在这里插入图片描述
那想一下,Fac(n)与Fac(n-1)与Fac(n-2)…等函数的空间地址是同一块空间吗?

综合上面的案例我们应该判断它们不是同一块空间的。

为什么呢?
上面的案例是F1函数调用完,结束后,再调用的F2函数
而阶乘递归是属于嵌套调用,每个函数都还没完全结束就又调用另一个函数了,所以它们开辟的空间肯定不一样,它们各自使用的空间都没有被操作系统收回过,怎么可能有其他函数又去占用这块空间呢。

而对案例修改一下,也可以让F1和F2函数的地址不一样,也就是在F1函数的内部去调用函数F2,这样它们的空间就不会重复了。

如下所示:

void F1()
{int a = 10;printf("%p\n", &a);F2();
}
void F2()
{int b = 10;printf("%p\n", &b);
}
int main()
{F1();return 0;
}

2.函数调用过程不清晰问题

案例3

这是一个斐波那契契递归Fib

long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}
int main()
{long long n;Fib(n);return 0;
}

你知道这个递归Fib函数的空间复杂度和时间复杂度吗?
Fib(n)函数每次返回两个函数Fib(n-1)+Fib(n-2).直到n<3时返回1.
也就是Fib函数每次调用都会又调用两个函数,而这个两个函数相当于又调用4个函数依次类推…最后应该调用2^n次
所以时间复杂度为O(2^n).
在这里插入图片描述
那空间复杂度呢?空间复杂度是多少呢?
有的人可能想呀,它不是相当于调用了2 ^ n次嘛,那不就是申请了2 ^ n个空间吗。真的是这样吗?

可能现在还有很多人没有搞清楚函数是怎么调用的,递归是怎么调用的。
有的人可能想是Fib(n)调用Fib(n-1)和Fib(n-2),然后操作系统就给Fib(n-1)和Fib(n-2)分配栈帧了,但其实不是。

函数的调用只有完全调用完才能去执行下一步
调用Fib(n-1)后,其实会继续往下面调用Fib(n-2),然后再往下调用Fib(n-3)直到调用到Fib(2),Fib(2)返回1后,Fib(2)也就结束,函数栈帧销毁,回到F(3),F(3)这时才开始调用F(1),F(1)返回1,F(1)的栈帧销毁,返回F(3),F(2)又开始调用了。依次类推

在这里插入图片描述
Fib(2)返回后,操作系统是不是就将它的空间回收了,然后又调用了Fib(1)所以Fib(1)开辟的空间就是刚刚操作系统收回的空间呀。
其实就是左边Fib(2)和右边F(1)用的是同一块空间。依次类推,Fib(4)返回后,空间被收回,然后操作系统又将空间分配给右边的Fib(3)使用。所以大体上左边和右边是共用一块空间,而左边是调用了n个空间,所以最后的空间大小是O(n).

3.总结

这三个个案例本质上就是要搞清楚函数栈帧是如何创建的以及如何销毁的

搞清楚函数是如何调用的,调用前操作系统要给函数分配栈帧,调用函数结束后,操作系统要将栈帧收回。
如果对函数栈帧方面有兴趣的可以阅读一下博主的《细谈函数栈帧的创建与销毁》。
还有我们可以发现:
时间是一去不复返的,不可再重复利用。
而空间是可以重复利用的。所以我们要特别重视算法的时间效率。

相关文章:

【研究空间复用及函数调用问题】

本篇总结函数调用过程会存在的一些奇怪现象&#xff0c;空间复用问题&#xff0c;其实本质上涉及函数调用的底层原理&#xff0c;理解函数栈帧的创建和销毁这样的问题直接迎刃而解。1.空间复用问题案例1案例22.函数调用过程不清晰问题案例33.总结1.空间复用问题 案例1 我们先…...

SQL常用查询语句

SELECT语句用于查询数据库中的内容 目录 1 查询指定表的所有内容 2 显示所有行的指定列 3 显示指定行的指定列 4 对查询结果进行排序 4.1 按照单一字段排序 4.2 多重排序 5 查询数据总数 5.1 查询一共有多少行 5.2 统计符合条件的有多少行 6 给查询出来的…...

【Python实战】一大波高颜值主播来袭:快看,某网站颜值排名,为了这个排名我可是大费周章啦,第一名不亏是你...(人脸检测+爬虫实战)

导语 民间一直有个传闻......「听说某站的小哥哥小姐姐颜值都很高哦&#xff01;」 &#xff08;不是颜值高才能加入&#xff0c;是优秀的人恰好颜值高&#xff09; 所有文章完整的素材源码都在&#x1f447;&#x1f447; 粉丝白嫖源码福利&#xff0c;请移步至CSDN社区或文末…...

Linux进程学习【三】

✨个人主页&#xff1a; Yohifo &#x1f389;所属专栏&#xff1a; Linux学习之旅 &#x1f38a;每篇一句&#xff1a; 图片来源 &#x1f383;操作环境&#xff1a; CentOS 7.6 阿里云远程服务器 Perseverance is not a long race; it is many short races one after another…...

Spring自动装配的底层逻辑

Spring是如何自动装配Bean的&#xff1f;看源码一些自己的理解&#xff0c;如有错漏&#xff0c;请指正 使用Spring之前我们要先去web.xml中设置一下Spring的配置文件&#xff0c;在Spring的配置文件中&#xff0c;是通过component-scan扫描器去扫描base-package底下所有的类装…...

华为OD机试 - 数组合并(C++) | 附带编码思路 【2023】

刷算法题之前必看 参加华为od机试,一定要注意不要完全背诵代码,需要理解之后模仿写出,通过率才会高。 华为 OD 清单查看地址:https://blog.csdn.net/hihell/category_12199283.html 华为OD详细说明:https://dream.blog.csdn.net/article/details/128980730 华为OD机试题…...

在vue3+ts的项目中,如何解决vant组件自带表单校验不生效?

问题描述&#xff1a; 点击发送验证码后&#xff0c;为了让逻辑更加严谨&#xff0c;使用了vant组件自带的表单校验&#xff0c;进行二次校验&#xff0c;防止验证码发送成功后&#xff0c;登录手机号被二次修改&#xff0c;但根据官网描述cv之后不生效&#xff0c;甚至连获取…...

华为OD机试真题Python实现【子序列长度】真题+解题思路+代码(20222023)

子序列长度 题目 有 N 个正整数组成的一个序列 给定一个整数sum 求长度最长的的连续子序列使他们的和等于sum 返回次子序列的长度 如果没有满足要求的序列 返回-1 🔥🔥🔥🔥🔥👉👉👉👉👉👉 华为OD机试(Python)真题目录汇总 ## 输入 两行输入 第一行…...

【答疑现场】我一个搞嵌入式的,有必要学习Python吗?

【答疑现场】我一个搞嵌入式的&#xff0c;有必要学习Python吗&#xff1f; 文章目录1 写在前面2 一个结论3 Python在嵌入式领域能干啥事4 Python是用来干大事的5 友情推荐6 福利活动大家好&#xff0c;我是架构师李肯&#xff0c;一个专注于嵌入式物联网系统架构设计的攻城狮。…...

MySQL存表报错问题 Incorrect string value

MySQL存表报错问题 Incorrect string value 问题 Incorrect string value: ‘\xF0\xA8\xA5\xA5\xE5\xAD…’ for column ‘xxxxxxx’ at row 1 意思是错误的字符&#xff0c;常出现在添加中文字符的时候。这个问题的产生原因主要是因为一些特色中文字符或者Emoji表情占4个字…...

SAP ABAP DIALOG长文本编辑框

1. 在SCREEN100 中创建一个定制控制(容器)&#xff0c;命名为PP *&---------------------------------------------------------------------* *& Report ZTEST_TEXT *& *&---------------------------------------------------------------------* *& *…...

电子技术——负反馈特性

电子技术——负反馈特性 本节我们进一步深入介绍负反馈特性。 增益脱敏性 假设 β\betaβ 是一个常数。考虑下面的微分方程&#xff1a; dAfdA(1Aβ)2dA_f \frac{dA}{(1 A\beta)^2} dAf​(1Aβ)2dA​ 将上式除以 AfA1AβA_f \frac{A}{1A\beta}Af​1AβA​ 得到&#xff1…...

网站移动端性能优化方法

移动端优化 click 的 300ms 延迟响应 click 的 300ms 延迟是由双击缩放(double tap to zoom)所导致的,由于用户可以进行双击缩放或者双击滚动的操作,当用户一次点击屏幕之后,浏览器并不能立刻判断用户是确实要打开这个链接,还是想要进行双击操作。因此,移动端浏览器就等…...

2023年AI语音会议汇总

2023年&#xff0c;AI语音领域学术会议精彩纷呈&#xff0c;语音之家汇总了国内外重要的会议呈现给大家&#xff0c;大家可根据时间统筹安排好2023年的学术活动交流行程。如果信息有误&#xff0c;欢迎指正。 ICASSP 2023 2023 IEEE International Conference on Acoustics, S…...

Mybatis持久层框架 | Mapper加载方式、目录结构解析

&#x1f497;wei_shuo的个人主页 &#x1f4ab;wei_shuo的学习社区 &#x1f310;Hello World &#xff01; Mapper(resource、class、package)加载方式 resource方式加载 通过resource或url加载单个mapper&#xff0c;接口文件与映射文件不在同一路径下&#xff0c;只能用re…...

九龙证券|创业板向未盈利企业敞开大门 考验投行估值定价能力

未盈余企业上市有了新选择。2月17日&#xff0c;全面实行股票发行注册制相关准则规矩发布施行。深交所发布《深圳证券交易所创业板股票上市规矩&#xff08;2023年修订&#xff09;》及《关于未盈余企业在创业板上市相关事宜的告诉》&#xff0c;“预计市值不低于50亿元&#x…...

「TCG 规范解读」第12章 TPM工作组 TCG身份验证研讨

可信计算组织&#xff08;Ttrusted Computing Group,TCG&#xff09;是一个非盈利的工业标准组织&#xff0c;它的宗旨是加强在相异计算机平台上的计算环境的安全性。TCG于2003年春成立&#xff0c;并采纳了由可信计算平台联盟&#xff08;the Trusted Computing Platform Alli…...

Logstash:在 Logstash 管道中的定制的 Elasticsearch update by query

我们知道 Elasticsearch output plugin 为我们在 Logstash 的 pipeline 中向 Elasticsearch 的写入提供了可能。我们可以使用如下的格式向 Elasticsearch 写入数据&#xff1a; elasticsearch {hosts > ["https://localhost:9200"]index > "data-%{YYYY.M…...

Spring Cloud Kubernetes环境下使用Jasypt

前言最近半年着手开始做了基于微服务的中台项目&#xff0c;整个项目的技术栈采用的是Java Spring Cloud Kubernetes Istio。业务开放上还是相当顺利的。但是在安全审核上&#xff0c;运维组提出了一个简易。现在项目一些敏感配置&#xff0c;例如MySQL用户的密码&#xff0…...

Kotlin-面向对象

本片博客主要写创建对象&#xff0c;创建接口&#xff0c;创建抽象类&#xff0c;data关键字的作用 创建对象 如何声明一个对象&#xff0c;使用class关键字 格式为&#xff1a; class 对象名字(对象属性名&#xff1a;属性类型…)&#xff5b;&#xff5d; 如果对象没有函数…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

【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…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...

Python 高效图像帧提取与视频编码:实战指南

Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...

【51单片机】4. 模块化编程与LCD1602Debug

1. 什么是模块化编程 传统编程会将所有函数放在main.c中&#xff0c;如果使用的模块多&#xff0c;一个文件内会有很多代码&#xff0c;不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里&#xff0c;在.h文件里提供外部可调用函数声明&#xff0c;其他.c文…...

如何把工业通信协议转换成http websocket

1.现状 工业通信协议多数工作在边缘设备上&#xff0c;比如&#xff1a;PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发&#xff0c;当设备上用的是modbus从站时&#xff0c;采集设备数据需要开发modbus主站&#xff1b;当设备上用的是西门子PN协议时&#xf…...