文档章节

算法的空间复杂度

浮躁的码农
 浮躁的码农
发布于 2015/08/19 20:08
字数 1730
阅读 24
收藏 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话:算法的空间复杂度

本文转载自:

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

浮躁的码农

粉丝 65
博文 747
码字总数 146196
作品 0
松江
程序员
私信 提问
算法的时间复杂度与空间复杂度分析

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

xy294636185
05/25
0
0
java 时间复杂度和空间复杂度

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

浮躁的码农
2015/08/13
0
1
[数据结构]基本概念、单链表操作

1.数据在内存中的存储方式 数据在计算机程序中都是存储在内存空间中的. 连续内存空间,比如申请一个数组,申请内存的大小事先知道。【数组】 非连续内存空间,特点是申请次数无限制,每次固定...

yaopan007
2015/08/28
0
0
时间复杂度和空间复杂度详解

算法的时间复杂度和空间复杂度合称为算法的复杂度。 1.时间复杂度 (1)时间频度 一 个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对...

cccyb
2016/10/08
14
0
算法基础-时间复杂度和空间复杂度(转载)

转自:http://blog.csdn.net/booirror/article/details/7707551 算法的时间复杂度和空间复杂度合称为算法的复杂度。 1.时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算...

banyoukang
2016/03/30
29
0

没有更多内容

加载失败,请刷新页面

加载更多

颜色模型与颜色应用---光的特性

电磁频谱 颜色的心理学特征

中国龙-扬科
22分钟前
2
0
android音频及强噪相关

Android AudioRecord和AudioTrack介绍(Android音频收集和播放 麦克风降噪) https://blog.csdn.net/tanningzhong/article/details/72844559 音频采集(AudioRecorder) https://www.jianshu.......

whoisliang
28分钟前
2
0
redis-持久化

RDB rdb持久化是把当前进程数据生成快照保存到磁盘的过程。触发RDB持久化过程分为手动触发和自动触发。 触发机制 bgsave执行流程 rdb优缺点 AOF 记录每次写命令,重启时再重新执行aof文件中的...

grace_233
33分钟前
3
0
电话激活Windows 中文操作系统步骤

已购买微软MAK批量授权,系统又在企业内网中,无法通过连接Internet进行激活,还可以通过电话完成激活。 前期准备 请提前准备好产品密钥,Product Key格式如下:XXXXX-XXXXX-XXXXX-XXXXX-XXX...

tonyfox
35分钟前
4
0
Apache用户认证,域名跳转,访问日志

Apache用户认证 当设置了用户认证后,用户访问网站时,需要输入用户名和密码才能访问。 可以全局设置,也可以为某几个虚拟主机单独配置。 下面以全局配置进行操作示例。 编辑httpd.conf进行配...

野雪球
39分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部