为什么归并排序空间复杂度是O(n)？
Hon*_*wal 3 memory algorithm mergesort space-complexity
乍一看，合并排序的空间复杂度为 O(n) 是有道理的，因为为了对未排序的数组进行排序，我要拆分并创建子数组，但所有子数组的大小总和将为 n。
问题：我主要关心的是递归期间 mergeSort() 函数的内存分配。我有一个主堆栈，对 mergeSort() （递归）的每个函数调用都将被推送到堆栈上。现在，每个递归调用的 mergeSort() 函数都将拥有自己的堆栈。因此，假设我们对 mergeSort() 进行了 5 次递归调用，那么主堆栈将包含 5 个函数调用，其中每个函数调用都有自己的函数堆栈。现在，每个函数堆栈都有自己的局部变量，例如函数创建的左子数组和右子数组。因此，5 个函数堆栈中的每一个在内存中都应该有 5 个不同的子数组。那么空间不应该随着递归调用的增长而增长吗？
Ste*_*tef 12
内存应该是线性的
尽管每次调用 mergeSort 都会触发两次递归调用，因此讨论和绘制递归调用的二叉树是有意义的，但一次只执行这两个递归调用之一；第一个呼叫在第二个呼叫开始之前结束。因此，在任何给定时间，只探索树的一个分支。“调用堆栈”代表这个分支。
递归树的深度最多为log(n)，因此调用堆栈的高度最多为log(n)。
探索一个分支需要多少内存？换句话说，在任何给定时间，最多在调用堆栈上分配多少内存？
在调用堆栈的底部，有一个大小为 n 的数组。
最上面是一个大小为 n/2 的数组。
最上面是一个大小为 n/4 的数组。
ETC...
因此调用堆栈的总大小最多为 n + n/2 + n/4 + ... < 2n。
因此调用堆栈的总大小最多为 2n。
可能存在内存泄漏
如果合并排序的实现在每次递归调用时分配一个新数组，并且您忘记在调用结束时释放这些数组，则分配的总内存将成为整个树所需的总内存，而不仅仅是一个分支。
考虑树中给定深度的所有节点。这些节点的子数组加起来形成整个数组。例如，树的根有一个长度为n的数组；然后再下一层，有两个子数组，代表原始数组的两半；再下一层，有四个子数组，代表原始数组的四分之四；等等。因此树的每一层都需要内存n。树有 log(n) 个级别。因此，为整棵树分配的内存总量将为 n log(n)。
结论
如果归并排序没有内存泄漏，那么它的空间复杂度是线性的O(n)。此外，可以（尽管并不总是需要）就地实现合并排序，在这种情况下，空间复杂度为常数O(1)（所有操作都直接在输入数组内执行）。
但是，如果您的合并排序实现存在内存泄漏，即您在递归调用中不断分配新数组，但在递归调用返回时不释放它们，那么它很容易具有空间复杂度O(n log n)。