空间复杂度

来自计算思维百科
跳转至: 导航搜索
空间复杂度.png

一个算法使用的存储空间越小,算法性能越好。空间复杂度算法的空间复杂度(Space Complexity)度量一个算法解决问题时需要的存储空间。

基本概念

算法的空间复杂度指的是,为了实现一个算法,要在计算机中额外分配临时空间使得算法能够运行,不包含输入数据占用的空间,也不包含实现该算法的程序代码和常数所占空间。算法的空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

例如:欧几里得算法

         输入:正整数 m,n

         输出:m,n的最大公约数

         1 r=m mod n;

         2 若r=0,输出最大公约数n;

         3 若r≠0,令m=n,n=r,转1继续。

上述欧几里得算法中,m,n是算法输入输出所占空间,r是欧几里得算法中的临时变量,也就是算法在运行过程中临时占用的存储空间。

应用范围

算法的空间复杂度在实际生活中可以指为解决问题需要的占地空间,也可以指为解决问题需要的人力资源。

应用案例-国王的婚姻

应用1- 搬运家具

案例:搬家的时候我们需要从货车上把家具搬到楼上,但是我们都是先把家具从货车上搬到楼下的空地上,然后再一件一件搬上楼。这里“楼下的空地”指的就是“搬家具”所需要的空间,我们用“楼下的空地”衡量“搬家具”方法的空间复杂度。

应用2-快递服务站点的设置

案例:一般快递都是由快递公司的快递员送货上门,但是在深圳大学,所有的快递都是放在杜鹃山快递服务站点,然后通知学生去站点取。快递从快递公司到我们手上需要开辟额外的空间来放快递,那么“杜鹃山快递服务站点”就是空间复杂度的一个度量。

应用3-助教的设置

案例:老师给一个班的学生上课就需要负责批改该班学生的作业,但是为了节约老师的时间,减轻老师的负担,学校会给老师配助教帮助老师批改学生作业。为了减少时间复杂度,增加增加空间复杂度-“助教”。

可以体现的计算思维

算法的空间复杂度和算法时间复杂度一样都是衡量算法好坏的重要指标。但是往往在实际情况中,时间效率和空间效率是相互矛盾的,经常出现“以空间换时间,以时间换空间”的情况,所以我们需要仔细权衡,用最适合当前情况的方法解决问题,体现了计算思维的“折中”特点。