算法的空间复杂度是指什么?

Question

如题所述

Answer 1

通常，当不用限定词地使用"复杂度"时，通常都是指时间复杂度。

算法的空间复杂度通过计算算法所需的存储空间实现。

记作：S(n)=O(f(n))。

其中，n为问题规模，f(n)为语句关于n所占存储空间的函数。

例如：

程序代码本身所占用的存储空间；

程序中如果需要输入输出数据，也会占用一定的存储空间；

程序在运行过程中，可能还需要临时申请更多的存储空间。

首先，程序自身所占用的存储空间取决于其包含的代码量，如果要压缩这部分存储空间，就要求我们在实现功能的同时，尽可能编写足够短的代码。

程序运行过程中输入输出的数据，往往由要解决的问题而定，即便所用算法不同，程序输入输出所占用的存储空间也是相近的。

事实上，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的临时存储空间。不同的算法所编写出的程序，其运行时申请的临时存储空间通常会有较大不同。

算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。

Answer 2

空间复杂度是指算法所需要消耗的内存空间。
参考资料：《大学计算机-计算思维导论》，清华大学出版社2019