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