堆排序的辅助空间与空间复杂度的差异？
堆排序的辅助空间与空间复杂度的差异？
提问于 2017-06-01 07:43:52
堆排序的辅助空间与空间复杂度的差异？
我的尝试：
如所解释的这里
如果我们想比较基于空间的标准排序算法，那么辅助空间将是一个比空间复杂性更好的标准。合并排序使用O(n)辅助空间，插入排序和堆排序使用O(1)辅助空间。然而，所有这些排序算法的空间复杂度都是O(n)。
我搜索了堆排序的空间复杂性，发现空间复杂度是O(1)。
我的问题是：
这个解释正确吗？辅助空间和空间复杂性有什么区别？
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-06-01 08:10:19
辅助性应用于所有未用于存储原始输入的内存。
堆排序输入是一个无序元素数组，它通过将它们重新排列为就地，这意味着不使用(或常量的)辅助空间(即不依赖于输入数组的大小)辅助空间(堆是使用输入数组-http://www.algostructure.com/sorting/heapsort.php构建的)。
谈到空间复杂性，您还应该考虑输入和辅助输入所使用的空间，因此在这个意义上，堆排序的空间复杂性为O(n)+O(1) (输入为n，而1为辅助空间)。公平地说，如果您想要的话，您也可以考虑堆栈上使用的空间(堆排序的递归实现使用这个空间，尽管应该只使用O(logn)，更多细节请看这里)。
顺便说一句，合并排序的辅助空间也可以是O(1)，因为存在一个合并排序的版本，它对数组进行排序(如何使用合并排序算法进行就地排序？)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/44301469
复制相关文章
相似问题
腾讯云开发者
