请问空间复杂度怎么计算？

Question

已经在网上查了两天关于空间复杂度的内容了，发现答案几乎都是很笼统的，可以举例说明如何计算空间复杂度吗？

Answer 1

简单来说，假设原始数据大小为n，一个算法需要m大小的内存才能运行，那么我们就有一个函数f(n)=m。这个函数去掉常数项和尾数项就是空间复杂度。
比如说，如果用冒泡排序对数据排序，如果直接在原始数据上排，那么根本不需要额外的存储空间，而最多只需要定义几个变量，那么复杂度就是1
如果排序产生一个新的数组，不修改原来的数组，那么对于排序n个数据，就需要n个新的存储空间，那么复杂度就是n。
再比如，对于两个数组，求它们的笛卡儿积（比如a=1,2,3 b=a,b，结果是1a 1b 2a 2b 3a 3b），那么它的复杂度就是n^2