数据结构与算法（Java版） | 算法的空间复杂度简介

关于算法的空间复杂度，下面我给大家作一个简单介绍。

类似于时间复杂度的讨论，一个算法的空间复杂度（Space Complexity）定义为该算法所耗费的存储空间，同样，它也是问题规模n的一个函数。

其实，空间复杂度就是对一个算法在运行过程中临时占用存储空间大小的量度，而这也就是说我们可以通过空间复杂度来计算出一个算法到底占用了多大的存储空间。

当然，这里我不得不说，有的算法需要占用的临时工作单元数是与解决问题的规模n有关的，就是它会随着n的增大而增大，当n较大时，就将占用较多的存储单元，例如快速排序和归并排序它俩就属于这种情况。

最后，还有一个注意点我得给大家说明一下，就是在做算法分析的时候，我们一般主要讨论时间复杂度。为何这么说呢？因为从用户使用体验上来看，他更看重的是程序执行的速度，而并不关心这个程序在运行期间到底占用了多大的存储空间。例如，大家熟悉的一些缓存产品（如Redis、Memcache）和算法（如基数排序），它们的本质就是用空间来换时间。

而且，大家也都知道，随着计算机的迅猛发展，硬件这一块的成本其实是在不断降低的，所以，在做算法优化的时候，一般来讲，用空间来换时间这种解决方案在公司里面都是被允许的。实际上，在我们做算法优化的时候，本身就需要能够用空间来换时间，你也不想想平时业务开发的时候为什么不直接去查数据库，而非要去做什么二级缓存、三级缓存？还不是希望速度能更快点，给用户的体验能更好点，对不！其实，做二级缓存、三级缓存的目的就是想让数据先加载到缓存，然后我们再直接从缓存中取，虽然这样做会占用一些额外的存储单元，但是速度却变得更快了。后面，在我们讲快速和归并这两个经典排序算法的时候，大家自然而然就会看到空间换时间这一个概念了。

至此，关于算法空间复杂度的基本介绍，我就给大家讲解完毕了。