堆排序中“辅助空间”和“空间复杂度”的区别是什么？

Question

堆排序中“辅助空间”和“空间复杂度”的区别是什么？

algorithmsortingheapsortspace-complexity

3

堆排序的辅助空间和空间复杂度之间有什么区别？

如此处所述：

如果我们想要比较标准的排序算法并且基于空间，那么辅助空间比空间复杂度更好。合并排序使用O(n)的辅助空间，插入排序和堆排序使用O(1)的辅助空间。尽管所有这些排序算法的空间复杂度都是O(n)。

我查找了堆排序的空间复杂度，发现其空间复杂度为O(1)。

我的问题是：

这个解释正确吗？辅助空间和空间复杂度之间有什么区别？

- Mithlesh Upadhyay

空间复杂度是否应该包括输入完全是基于个人观点的（因此不适合在Stack Overflow上提问）。我看到的99.9%的空间复杂度都不包括输入，这可能是因为在算法开始之前已经分配了空间，所以包括这些空间并没有太多意义。显然，如果将输入的n个元素包括在内，说一个算法使用O(1)空间是毫无意义的（因为n个元素不是O(1)）。 - Bernhard Barker

1个回答

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

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

- Davide Spataro · Accepted Answer

Auxiliary 指的是所有未用于存储原始输入的内存。

堆排序的输入是无序元素数组，它通过在原地重新排列这些元素来工作，意味着没有（或者只有常量数量的即不取决于输入数组大小的辅助空间被使用）（堆是使用输入数组构建的-http://www.algostructure.com/sorting/heapsort.php）。

在考虑空间复杂度时，还应考虑输入和辅助空间使用的空间，因此从这个意义上讲，堆排序的空间复杂度为 O(n)+O(1)（n为输入，1为辅助空间）。公平起见，如果你愿意，你也可以考虑堆排序递归实现使用的堆栈空间，尽管它应该只有O(logn)（更多细节请参阅此处）。

顺便提一下，归并排序的辅助空间也可以为O(1)，因为存在一种对数组进行原地排序的merge-sort版本（如何使用归并排序算法原地排序？）。