算法空间复杂度计算

news/2024/5/30 2:17:23/文章来源:https://blog.csdn.net/lovedingd/article/details/136674177

目录

空间复杂度定义

影响空间复杂度的因素

算法在运行过程中临时占用的存储空间讲解

例子

斐波那契数列递归算法的性能分析

二分法(递归实现)的性能分析


空间复杂度定义

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
一个算法在计算机存储器上所占用的存储空间,包括程序代码所占用的空间输入数据所占用的空间辅助变量所占用的空间这三个方面。

影响空间复杂度的因素

注意:
一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法,其空间复杂度为递归所使用的堆栈空间的大小。它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1,这个1表示开始进行的一次非递归调用)
递归的空间复杂度: 每次递归所开空间*深度。

算法在运行过程中临时占用的存储空间讲解

1、有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地”进行的,是节省存储的算法,下面会介绍。

2、有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况。

计算方法
①忽略常数,用O(1)表示
②递归算法的空间复杂度=递归深度n*每次递归所要的辅助空间
③对于单线程来说,递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数,因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。

为什么要求递归的深度呢?

        因为每次递归所需的空间都被压到调用栈里(这是内存管理里面的数据结构,和算法里的栈原理是一样的),一次递归结束,这个栈就是就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。

例子

1、空间算法的常数阶

如上图,这里有三个局部变量分配了存储空间,所以f(n) = 1 + 1 + 1 = 3,根据上面的法则该函数不受n的影响且为常数项,所以空间复杂度记作O(1)。这种与问题的大小无关(n的多少),执行时间恒定的算法,我们称之为具有O(1)的空间复杂度,又叫常数阶。

2、两个函数,空间复杂度分别为O(1), O(n)

# O(1)
def f1(n):j = 0for i in range(n):j += 1return j# O(n)
def f2(n):a = []for i in range(n):a.append(i)return a

在第一个函数中,所需开辟的内存空间并不会随着n的变化而变化,即此算法空间复杂度为一个常量,所以表示为O(1)。在第二个函数中,随着n的增大,开辟的内存大小呈线性增长,这样的算法空间复杂度为O(n)。在递归的时候,会出现空间复杂度为logn的情况,比较特殊。

3、空间算法的线性阶(递归算法)

如上图,这是一个递归算法(计算从n + (n-1) + (n-2) + … + 2 + 1的和)
每当执行一次该函数就会为tmp分配一个临时存储空间,所以f(n) = 1*(n-1+1) = n,函数是受n影响的所以空间复杂度记为O(n)

斐波那契数列递归算法的性能分析

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……
这个数列从第3项开始,每一项都等于前两项之和。

如果设F(n)为该数列的第n项(n∈N*),那么这句话可以写成如下形式::F(n)=F(n-1)+F(n-2)

显然这是一个线性的递推数列。

通项公式 :

上面就是斐波那契数列的递推公式,这样一个完全是自然数的数列,通项公式却是用无理数来表达的。而且当n趋向于无穷大时,前一项与后一项的比值越来越逼近黄金分割0.618

​​​​​​​

递推是公式是求解斐波那契数列的一个方法,我们当然也可以用计算机编写程序来求解。

方法一(迭代法)
  /// <summary>/// 斐波那契(迭代法)/// </summary>/// <param name="n"></param>/// <returns></returns>int Fibonacci(int n){if (n <= 0)return -1;if (n == 1 || n == 2)return 1;else{int num = 0;int a = 1;int b = 1;while (n - 2 > 0){num = a + b;a = b;b = num;n--;}return num;}}

时间复杂度:
while以外的算法语句都忽略不计(不随n的变化而变化)
while算法语句所有语句
f(n) = 4 *(n - 2) = 4n - 8
时间复杂度记为:O(n)

空间复杂度:
算法中num、a、b只创建1次
s(n) = 1 + 1 + 1 = 3
空间复杂度记为:O(1)

方法二(递归法)

def fibonacci(n):if n <= 0:return 0elif n == 1:return 1else:return fibonacci(n - 1) + fibonacci(n - 2)

首先回顾一下时间复杂度:递归算法的时间复杂度 = 递归的次数 * 每次递归中的操作次数。每次递归进行了一次加法操作,时间复杂度是O(1),递归的次数可以抽象成一棵递归树:(以n=5为例)

在这棵二叉树中每一个节点都是一次递归,一棵深度(按根节点深度为1)为k的二叉树最多可以有  个节点,所以该递归算法的时间复杂度为O(2^n),这个复杂度是非常大的,随着n的增大,耗时是指数上升的。

然后再来看空间复杂度:递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度。

为什么要求递归的深度呢?因为每次递归所需的空间都被压到调用栈里(这是内存管理里面的数据结构,和算法里的栈原理是一样的),一次递归结束,这个栈就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。

回到斐波那契数列的例子,每次递归所需要的空间大小都是一样的,所以每次递归中需要的空间是一个常量,并不会随着n的变化而变化,每次递归的空间复杂度就是 O(1)。递归的深度如图所示:

递归第n个斐波那契数的话,递归调用栈的深度就是n。那么每次递归的空间复杂度是O(1), 调用栈深度为n,所以这段递归代码的空间复杂度就是O(n)。

此算法时间复杂度非常高的主要原因是最后一行的两次递归,所以优化算法的方向就是减少递归的调用次数:

def fibonacci(first, second, n): #初始值 first = second = 1if n <= 0:return 0elif n <= 2:return 1elif n == 3:return first + secondelse:return fibonacci(second, first + second, n - 1)

举例来说 n=5 时 fibonacci(1,1,5) → fibonacci(1,2,4) → fibonacci(2,3,3) → 2+3=5。这里相当于用first和second来记录当前相加的两个数值,此时就不用两次递归了。因为每次递归的时候n减1,即只是递归了n次,所以时间复杂度是 O(n)。同理递归的深度是n-2,每次递归所需的空间还是常数,所以空间复杂度依然是O(n)。

最后总结一下:

可以看出,求斐波那契数的时候,使用递归算法并不一定在性能上是最优的,但递归确实简化了代码层面的复杂度。

二分法(递归实现)的性能分析

方法一(迭代法)
	/// <summary>/// 二分查找/// </summary>/// <param name="arr">查找数组</param>/// <param name="len">数组长度</param>/// <param name="num">查找项</param>/// <returns></returns>int BinarySearch(int[] arr,int len,int num){int left = 0;int right = len - 1;int mid;while (left <= right){mid = (left + right) / 2;if (arr[mid] > num)right = mid - 1;else if (arr[mid] < num)left = mid + 1;elsereturn mid;}return -1;}

时间复杂度:
left、right、mid运算次数
f(n1) = 1 + 1 + 1 = 3
我们将While循环中的运算作为一个整体看待,每次都是折半运算次数
f(n2) = log2^n
总运行次数
f(all) = f(n1)+f(n2) = 3 + log2 ^ n
时间复杂度记为:O(log2^n)

空间复杂度:
算法中left、right、mid只创建的次数
s(n) = 1 + 1 + 1 = 3
空间复杂度记为:O(1)

方法二(递归法)

def binary_search(arr, l, r, x):if r >= l:mid = l + (r - l) // 2if arr[mid] == x:return midelif arr[mid] > x:return binary_search(arr, l, mid - 1, x)else:return binary_search(arr, mid + 1, r, x)else:return -1

此算法时间复杂度为O(logn)。每次递归的空间复杂度主要就是参数里传入的这个arr数组,但需要注意的是在C/C++中函数传递数组参数,不是整个数组拷贝一份传入函数而是传入数组首元素地址。也就是说每一层递归都是公用一块数组地址空间的,所以每次递归的空间复杂度是常数即:O(1)。(Python呢?)再来看递归的深度,二分查找的递归深度是logn ,递归深度就是调用栈的长度,那么这段代码的空间复杂度为 1 * logn = O(logn)。

注意:关注语言在传递函数参数时,是拷贝整个数值还是拷贝地址,如果是拷贝整个数值那么该二分法的空间复杂度就是O(nlogn)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1007144.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

电脑干货:6款免费的实用工具,值得收藏

目录 1、HelloWindows 2、Memory Helper 3、MindNode 4、B站视频下载工具 5、wallhaven壁纸 1、HelloWindows HelloWindows是一个纯净Windows系统下载网站&#xff0c;它可以下载到所有Windows系统源文件&#xff0c;比如Windows11、Windows10、win7、XP等&#xff0c;也可…

0基础安装Burpsuit专业版

首先先安装java环境,安装jdk 11的版本 文件中2023版的可以直接点开使用不需要复杂的操作的步骤 资源获取链接&#xff1a; 链接&#xff1a;百度网盘 请输入提取码 提取码&#xff1a;k2qq 其中&#xff1a;1号文件是bp的英文版激活包&#xff0c;-2号是中文版汉化版的激活包…

基于FPGA加速的bird-oid object算法实现

导语 今天继续康奈尔大学FPGA 课程ECE 5760的典型案例分享——基于FPGA加速的bird-oid object算法实现。 &#xff08;更多其他案例请参考网站&#xff1a; Final Projects ECE 5760&#xff09; 1. 项目概述 项目网址 ECE 5760 Final Project 模型说明 Bird-oid object …

Tree Shaking:优化前端项目的利器

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

汽车IVI中控开发入门及进阶(十四):功能安全

前言: 是时候需要来说一下功能安全了,有没有发现现在很多主机厂、Tier1对芯片等BOM物料有些是有功能安全需求的,那么什么是功能安全呢? 车辆中电子元件数量的增加增加了更多故障的可能性,对驾驶员和乘客的风险更高。这种风险的增加导致汽车行业将功能安全标准作为汽车设计…

C#,数值计算,矩阵相乘的斯特拉森(Strassen’s Matrix Multiplication)分治算法与源代码

Volker Strassen 1 矩阵乘法 矩阵乘法是机器学习中最基本的运算之一,对其进行优化是多种优化的关键。通常,将两个大小为N X N的矩阵相乘需要N^3次运算。从那以后,我们在更好、更聪明的矩阵乘法算法方面取得了长足的进步。沃尔克斯特拉森于1969年首次发表了他的算法。这是第…

什么是测试自动化平台?为什么需要测试自动化平台?如何选择平台

什么是测试自动化平台&#xff1f; 测试自动化平台是一种软件工具或框架&#xff0c;可帮助软件开发团队实现测试流程的自动化。它集成了多种功能和工具&#xff0c;使测试人员能够更高效地进行测试计划、用例设计、测试执行和结果分析。 为什么需要测试自动化平台&#xff1f…

微信小程序-day01

文章目录 前言微信小程序介绍 一、为什么要学习微信小程序?二、微信小程序的历史创建开发环境1.注册账号2.获取APPID 三、下载微信开发者工具1.创建微信小程序项目2.填写相关信息3.项目创建成功 四、小程序目录结构项目的主体组成结构 总结 前言 微信小程序介绍 微信小程序&…

3.环境对象this、this指向总结(待完成还有节流防抖待完成)、回调函数、事件

环境对象this 环境对象本质上是一个关键字 this this所在的代码区域不同&#xff0c;代表的含义不同 全局作用域中的this 全局作用域中this代表window对象 局部作用域中的this 在局部作用域中(函数中)this代表window对象 函数直接调用的时候简写了&#xff0c;函数完整写法…

网络编程:网络编程基础

一、网络发展 1.TCP/IP两个协议阶段 TCP/IP协议已分成了两个不同的协议&#xff1a; 用来检测网络传输中差错的传输控制协议TCP 专门负责对不同网络进行2互联的互联网协议IP 2.网络体系结构 OSI体系口诀&#xff1a;物链网输会示用 2.1网络体系结构概念 每一层都有自己独…

【python】anaconda安装过程

【运行环境】Windows11 文章目录 一、anaconda下载二、anaconda安装三、环境变量配置四、测试环境变量是否配置成功五、总结 一、anaconda下载 1、输入网址“https://www.anaconda.com”进入Anaconda官网。 2、找到【Free Download】点击进入&#xff1a; 3、点击对应系统的…

【论文速读】 | DeGPT:通过大语言模型优化反编译器输出

本次分享论文为&#xff1a;DeGPT: Optimizing Decompiler Output with LLM 基本信息 原文作者&#xff1a;Peiwei Hu, Ruigang Liang, Kai Chen 作者单位&#xff1a;中国科学院信息工程研究所&#xff1b;中国科学院大学网络空间安全学院 关键词&#xff1a;反向工程&…

【自然语言处理】NLP入门(五):1、正则表达式与Python中的实现(5):字符串常用方法:对齐方式、大小写转换详解

文章目录 一、前言二、正则表达式与Python中的实现1.字符串构造2. 字符串截取3. 字符串格式化输出4.字符转义符5. 字符串常用函数函数与方法之比较 6. 字符串常用方法1. 对齐方式center()ljust()rjust() 2. 大小写转换lower()upper()capitalize()title()swapcase() 一、前言 本…

ModuleNotFoundError: No module named ‘sklearn.cross_validation‘

一、问题分析 ModuleNotFoundError: No module named sklearn.cross_validation 英文先翻译一遍&#xff0c;模块未找到问题&#xff0c;这里涉及到sklearn这个模块&#xff0c;Sklearn &#xff08;全称 SciKit-Learn&#xff09;&#xff0c;是基于 Python 语言的机器学习工…

mysql如何开启手动提交事务

在mysql中&#xff0c;有一个变量autocommit&#xff0c;表示自动提交&#xff0c;默认为1&#xff0c;表示开启自动提交。通过以下命令查询 select autocommit;当autocommit为1时&#xff0c;任何一条sql语句都是一个事务&#xff0c;执行完由mysql自动提交。如果想自己决定什…

鸿蒙实战开发学习:【HiView插件开发】

概述 Hiview是一个跨平台的终端设备维测服务集&#xff0c;其中是由插件管理平台和插件实现的各自功能构成整套系统。 本文描述了hiview插件开发的全部流程。 插件的概念 整节部分包括了插件的概念&#xff0c;事件源的概念&#xff0c;流水线的概念等基本概念 插件的定义 …

【SpringCloud微服务实战01】Eureka 注册中心

前言 在 Eureka 架构中&#xff0c;微服务角色有两类&#xff1a; EurekaServer &#xff1a;服务端&#xff0c;注册中心 记录服务信息 心跳监控 EurekaClient &#xff1a;客户端 Provider &#xff1a;服务提供者&#xff0c;例如案例中的 user-service …

吴恩达机器学习笔记 十八 制定一个性能评估标准 学习曲线 高偏差 高方差

一个模型的好坏的评估基准可以从下面几个方面考虑&#xff1a; 1.考虑人类在这个问题上的表现 2.对比竞争算法的表现 3.根据经验猜测 判断是高偏差还是高方差 训练样本数量越多&#xff0c;越难完美地拟合每个样本&#xff0c;因此 J_train 会逐渐增大一点点&#xff0c;但泛…

创造一款安卓自定义控件(4)——使用Matrix的setPolyToPoly方法实现图像纠正

接上文&#xff1a; 创造一款安卓自定义控件_任意4顶点裁剪框http://t.csdnimg.cn/vu1r5 创造一款安卓自定义控件_任意4顶点裁剪框2_为裁剪框添加放大镜功能http://t.csdnimg.cn/qkngh 创造一款安卓自定义控件_裁剪原理介绍http://t.csdnimg.cn/ORRRL 需求 随着需求修改&#x…

Apache Doris 2.1.0 版本发布:开箱盲测性能大幅优化,复杂查询性能提升 100%

亲爱的社区小伙伴们&#xff0c;我们很高兴地向大家宣布&#xff0c;在 3 月 8 日我们引来了 Apache Doris 2.1.0 版本的正式发布&#xff0c;欢迎大家下载使用。 在查询性能方面&#xff0c; 2.1 系列版本我们着重提升了开箱盲测性能&#xff0c;力争不做调优的情况下取得较好…