如何计算堆排序的空间复杂度 [英] How to calculate space complexity for heapsort

问题描述

我知道堆排序的空间复杂度为 O(1).但是对于递归程序，在计算空间复杂度时，它的深度，即它进行的递归调用次数也很重要.因此，相同代码的迭代和递归方法的空间复杂度不同.那么在递归处理时，堆排序的空间复杂度是多少?

I know that space complexity for a heap sort it O(1). But for a recursive program when calculating space complexity, the depth it goes i.e., number of recursive call it makes also counts. So space complexity for iterative and recursive approach for the same code differs. So what would be the space complexity for heap sort when approached recursively ?

推荐答案

当使用递归实现 heapify 函数时，它看起来像这样的伪代码:

When the heapify function is implemented using recursion, it will look something like this pseudo code:

heapify(arr, n, root): 
    largest = root 
    left = 2*root + 1 
    right = 2*root + 2
    if left < n && arr[left] > arr[largest]: largest = left
    if right < n && arr[right] > arr[largest]: largest = right 
    if largest != root:
        swap(arr[root], arr[largest])
        heapify(arr, n, largest)

回想一下，heapify 函数用于首先将数组转换为堆，然后使用减小大小的堆对数组进行排序.

To recall, the heapify function is used to first turn the array into a heap and then to order the array with a heap that reduces in size.

需要注意的是，递归模式归结为尾递归.根据语言功能，这可以在不使用调用堆栈的情况下执行(其中使用的空间随着每次递归调用而增加).

It is important to note that the recursion pattern comes down to tail recursion. Depending on the language capabilities this can be executed without the use of a call stack (of which the used space increases with each recursive call).

因此，除非递归算法还定义了递归调用应该如何在幕后"实现——可能排除尾递归机制——，它仍然可以是用 O(1) 空间实现.

So unless the recursive algorithm also defines how a recursive call should be implemented "under the hood" -- possibly excluding tail recursion mechanics --, it can still be implemented with O(1) space.

然而，如果不使用尾递归，则应考虑递归深度.该深度至多是(堆)树的深度，即 logn.

If however tail recursion is not used, then the recursion depth should be taken into account. That depth is at most the depth of the (heap) tree, which is logn.

这篇关于如何计算堆排序的空间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！