空间复杂度

代码随想录笔记：

空间复杂度：

对一个算法在运行过程中占用内存空间大小的量度。注意对于与算法无关的空间不算入时间复杂度，例如存储某些输入的数组。

不要以为空间复杂度就已经精准的掌握了程序的内存使用大小，很多因素会影响程序真正内存使用大小，例如编译器的内存对齐，编程语言容器的底层实现等等这些都会影响到程序内存的开销。所以空间复杂度是预先大体评估程序内存使用的大小。

递归的空间复杂度 = 递归最大深度（递归调用栈最大深度）* 每次递归的空间复杂度 。

首先知道递归的空间复杂度来自于递归时开辟的递归栈，栈的层数=递归的次数，每调用递归一次就压栈一次，递归返回就出栈一次。因为递归栈空间是会重复利用的，所以我们只需要求递归最大时栈的层数。