空间复杂度合并排序，插入排序说明(适用于虚拟对象)

Question

我想知道是否有人可以向我解释这两个算法的空间复杂性是如何工作的。我已经读过了，但如果我理解正确的话，它们似乎是矛盾的。

例如，我对链表将如何影响空间复杂性感兴趣，这个问题说它使其更快？；Why is mergesort space complexity O(log(n)) with linked lists?

然而，这个问题说这无关紧要；Merge Sort Time and Space Complexity

现在我对编程有点新手，我想更好地理解这个理论，这样哑巴语言就会很受欢迎。

Answer 1

合并排序的总空间复杂度是O(n)，因为您必须将元素存储在某个地方。然而，在数组实现和链表实现之间，确实可以在额外的空间复杂性方面存在差异。

请注意，您可以实现一个只需要O(1)额外空间的迭代版本。然而，如果我没记错的话，这个版本的性能会很糟糕。

在传统的递归版本中，您需要考虑堆栈帧。仅此一点就给了O(log n)额外的空间需求。

在链表实现中，您可以在没有任何辅助内存的情况下就地执行合并。因此，O(log n)的额外空间复杂性。

在数组实现中，合并需要辅助内存(可能是辅助数组)，而最后一次合并所需的内存量与最初用于存储元素的内存量相同。因此，O(n)的额外空间复杂性。

请记住，空间复杂性告诉您算法的空间需求如何随着输入大小的增长而增长。有些细节是空间复杂性忽略的。也就是说，堆栈帧和元素的大小可能不同，并且由于链接(引用)，链表比数组占用更多的空间。最后一个细节对于小元素很重要，因为数组实现的额外空间需求可能少于链表实现的链接占用的额外空间。

Answer 2

为什么合并排序空间复杂度为O(log(n))与链表？

这只适用于链表的自顶向下合并排序，其中由于递归而使用O(log2(n))堆栈空间。对于链表的自底向上合并排序，空间复杂度为O(1) (常量空间)。用于链表的优化的自底向上合并排序的一个示例使用指向列表的第一个节点的指针或引用的小(26到32)数组。这仍然被认为是O(1)空间复杂度。链接到wiki文章中的伪代码：

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists