文档章节

算法的空间复杂度

浮躁的码农
 浮躁的码农
发布于 2015/08/19 20:08
字数 1730
阅读 25
收藏 0

类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。

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

我们在写代码时,完全可以用空间来换取时间,比如说,要判断某某年是不是闰年,你可能会花一点心思写了一个算法,而且由于是一个算法,也就意味着,每次给一个年份,都是要通过计算得到是否是闰年的结果。还有另一个办法就是,事先建立一个有2 050个元素的数组(年数略比现实多一点),然后把所有的年份按下标的数字对应,如果是闰年,此数组项的值就是1,如果不是值为0。这样,所谓的判断某一年是否是闰年,就变成了查找这个数组的某一项的值是多少的问题。此时,我们的运算是最小化了,但是硬盘上或者内存中需要存储这2050个0和1。

算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地"进行的,是节省存储的算法,如这一节介绍过的几个算法都是如此;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如将快速排序和归并排序算法就属于这种情况。

通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好,其实要看你用在什么地方。

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)= O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。

一般情况下,一个程序在机器上执行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为O(1)。

  • 关于O(1)的问题, O(1)是说数据规模和临时变量数目无关,并不是说仅仅定义一个临时变量。举例:无论数据规模多大,我都定义100个变量,这就叫做数据规模和临时变量数目无关。就是说空间复杂度是O(1)。

  • 那就是指函数运行时处理数据的规模与空间和时间的一个变化时的比例关系,不是具体的数值。

当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(10g2n);当一个算法的空I司复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

  • 通常,我们都使用“时间复杂度”来指运行时间的需求,使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时,通常都是指时间复杂度。

对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。

延伸阅读

此文章所在专题列表如下:

  1. 第一话:你的数据结构怎么学的?
  2. 第二话:数据结构的历史与来由
  3. 第三话:关于数据结构的一些概念
  4. 第四话:数据的逻辑结构
  5. 第五话:数据的物理结构
  6. 第六话:关于数据类型
  7. 第七话:抽象数据类型ADT
  8. 第八话:补充数据结构基本概念的关系
  9. 第九话:数据结构与算法的关系
  10. 第10话:什么是算法?
  11. 第11话:算法的五个基本特征
  12. 第12话:什么样的算法才是好算法
  13. 第13话:算法的性能分析
  14. 第14话:如何计算算法的时间复杂度
  15. 第15话:算法的最坏情况与平均情况
  16. 第16话:算法的空间复杂度

本文转载自:

共有 人打赏支持
浮躁的码农

浮躁的码农

粉丝 66
博文 770
码字总数 148307
作品 0
松江
程序员
私信 提问
java 时间复杂度和空间复杂度

同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。 算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是度...

浮躁的码农
2015/08/13
0
1
时间空间复杂度的解释

何为时间空间复杂度? 《1》空间复杂度O(N): 一个算法在运行过程中临时占用存储空间大小的量度。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表...

YKIT
2015/10/14
69
0
算法的学习-基础

前言 在参加面试的时候,多多少少都会问到一些关于算法的知识。 这其实是有原因的:在多个人专业知识相同的情况下,公司为什么选择放弃他人而选择你,其中的一个因素就是看你的算法基础。 本...

黑色小老虎丶
2017/11/17
0
0
算法的时间复杂度与空间复杂度分析

算法的时间性能分析 1.算法消耗的时间 一个算法的执行时间是指算法中所有语句执行时间的总和。每条语句的执行时间等于该条语句的执行次数乘以执行一次所需实际时间。 由于语句的执行要由源程...

xy294636185
2018/05/25
0
0
算法时间复杂度和空间复杂度的计算

算法,即解决问题的方法。同一个问题,使用不同的算法,虽然得到的结果相同,但是耗费的时间和资源是不同的。 就比如要拧一个螺母,使用扳手还是钳子是有区别的,虽然使用钳子也能拧螺母,但...

tr_ainiyangyang
2018/04/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

给windows server中的“未识别的网络”或“无法识别的网络”设置网络位置类型

在windows server中,如果网络没有被正确的识别,那么就需要手工设置一下网络位置类型。 将“公用网络”指定设置为“专用网络“ 【控制面板】--【系统和安全】--【管理工具】--【本地安全策略...

gugudu
50分钟前
1
0
阿里强制要求的21条Java开发规范,可以避免很多坑

1. 【强制】避免通过一个类的对象引用访问此类的静态变量或静态方法,无谓增加编译器解析成本,直接用类名来访问即可。 2. 【强制】所有的覆写方法,必须加@Override注解。 说明:getObject...

天王盖地虎626
今天
7
0
oracle dg 备库未设置convert参数导致ORA-01111,ORA-01110

查看trace 文件: MRP0: Background Managed Standby Recovery process started (amls) started logmerger process Sun Jan 20 07:55:53 2019 Managed Standby Recovery starting Real Time ......

hnairdb
今天
2
0
乱入Linux界的我是如何学习的

欢迎来到建哥学Linux,咳!咳!咳!开个玩笑哈,我是一个IT男,IT界的入门选手,正在学习Linux。 在之前,一直想进军IT界,学习IT技术,但是苦于没有人指导,也不知道学什么,最开始我自己在...

linux-tao
今天
2
0
乱入Linux界的我是如何学习的

欢迎来到建哥学Linux,咳!咳!咳!开个玩笑哈,我是一个IT男,IT界的入门选手,正在学习Linux。 在之前,一直想进军IT界,学习IT技术,但是苦于没有人指导,也不知道学什么,最开始我自己在...

linuxprobe16
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部