书上的定义是这样的:一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间。但有这样一道练习题:算法的空间复杂度是指()。A,算法程序所占的存储空间。B,执行算法需要的内存空间。根据书上的定义,答案应该选择B,但习题给的答案却是A,习题答案的解析是:空间复杂度是指算法程序所需的存储空间。所以,我矛盾了。去网上找答案有的说A对,有的说B对,但没有一个给出具体原因的。希望有人能够详细解释下究竟什么是算法的空间复杂度,谢谢。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。
而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。
类似于 时间复杂度的讨论,一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。
分析
分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说,一般都比较简短,算法本身所占用的存储空间较少,但运行时需要一个附加堆栈,从而占用较多的临时工作单元;
若写成非递归算法,一般可能比较长,算法本身占用的存储空间较多,但运行时将可能需要较少的存储单元。
一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。
若一个算法为递归算法,其空间复杂度为递归所使用的堆栈空间的大小,它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1,这个1表示开始进行的一次非递归调用)。
参考资料来源:百度百科—空间复杂度