我知道堆的空间复杂度是O(1)。但是对于递归程序,当计算空间复杂度时,它所需的深度即递归调用的数量也可以计算。因此,对于相同的代码,迭代和递归方法的空间复杂度不同。那么,递归时,堆排序的空间复杂度是多少?

最佳答案

当使用递归实现heapify函数时,它将类似于以下伪代码:

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函数用于首先将数组转换为堆,然后使用大小减小的堆对数组排序。
值得注意的是,递归模式可以归结为tail recursion这取决于语言能力,可以在不使用调用堆栈的情况下执行(其中使用的空间随着每次递归调用而增加)。
因此,除非递归算法还定义了递归调用应该如何“在幕后”实现(可能不包括尾部递归机制),否则它仍然可以用O(1)空间实现。
但是,如果不使用尾部递归,则应考虑递归深度。这个深度最多是(堆)树的深度,即logn。

07-24 09:47
查看更多