为什么归并排序的空间复杂度是O(n)？

Question

为什么归并排序的空间复杂度是O(n)？

algorithmmemorymergesortspace-complexity

3

乍一看，归并排序的空间复杂度为O(n)是有道理的，因为为了对未排序的数组进行排序，我正在拆分和创建子数组，但所有子数组大小的总和将为n。

问题：我主要关心的是在递归期间mergerSort()函数的内存分配。我有一个主堆栈，并且每个对mergerSort()的函数调用（递归）都将被推送到堆栈上。现在，每次递归调用mergeSort()函数都会有自己的堆栈。因此，假设我们已经对mergeSort()进行了5次递归调用，则主堆栈将包含5个函数调用，其中每个函数调用都有自己的函数堆栈。现在，每个函数堆栈都将具有其自己的局部变量，例如函数创建的左子数组和右子数组。因此，这5个函数堆栈中的每一个都应该在内存中具有5个不同的子数组。因此，随着递归调用的增加，空间是否会增长？

- black sheep 369

2

如果在每个递归调用中分配新的子数组，则总内存使用量将为O(n log n)。但是，在MergeSort中没有必要分配新的数组；它可以完全就地完成。在这种情况下，唯一需要的额外空间是堆栈，其为O(log n)。 - Thomas

@Thomas - 有一些迭代版本的原地归并排序，其总空间复杂度为O(1)，比使用第二个数组（O(n)空间）的归并排序慢约50％。一个例子是grailsort.h。 - rcgldr

@rcgldr 我不知道那500多行代码在干什么，但它看起来不像归并排序。 - Thomas

@Thomas - 那段代码是针对“原地”归并排序进行了多次优化的结果。请查看“无缓冲区”的例程。带有缓冲区的例程使用一个小的固定大小缓冲区来加速，这仍然是O(1)空间（因为它是一个固定大小的缓冲区），但正常的目标是不使用任何缓冲区的原地归并排序。二分查找是作为合并的一部分完成的，找到元素所属的位置，然后“旋转”子数组以将元素放置在正确的位置。在代码底部是“经典”的原地归并排序。 - rcgldr

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stef · Accepted Answer

内存应该是线性的

尽管每次调用mergeSort都会触发两个递归调用，因此可以谈论和绘制递归调用的二叉树，但只有那两个递归调用中的一个被一次执行；第一个调用在第二个调用开始之前结束。因此，在任何给定时间，只有一棵树枝正在被探索。"调用堆栈"表示这个分支。

递归树的深度最多为log(n)，因此调用堆栈的高度最多为log(n)。

在探索一个分支时需要多少内存？换句话说，在任何给定时间，调用堆栈上最多分配了多少内存？

在调用堆栈的底部，有一个大小为n的数组。

在它上面是一个大小为n/2的数组。

再往上是一个大小为n/4的数组。

等等......

因此，调用堆栈的总大小最多为n + n/2 + n/4 + ... < 2n。

因此，调用堆栈的总大小最多为2n。

可能存在内存泄漏问题

如果您的归并排序实现在每次递归调用时分配一个新数组，并且您在调用结束时忘记释放这些数组，则分配的总内存将变为整棵树所需的总内存，而不仅仅是一个分支。

考虑树中给定深度的所有节点。这些节点的子数组加起来形成整个数组。例如，树的根具有长度为n的数组；然后在其下方一层，有两个表示原始数组的两半的子数组；然后在其下方一层，有四个表示原始数组四分之一的子数组；等等。因此，树的每个级别都需要内存n。树有log(n)级别。因此，为整棵树分配的总内存量将是n log(n)。

结论

如果归并排序没有内存泄漏，则其空间复杂度为线性O(n)。此外，可以（尽管不总是可取）就地实现归并排序，在这种情况下，空间复杂度为恒定的O(1)（所有操作都直接在输入数组内执行）。

但是，如果您的归并排序实现存在内存泄漏问题，即在递归调用中保留了新数组的分配，但在递归调用返回时没有释放它们，则它很容易具有空间复杂度O(n log n)。