堆排序空间复杂度的计算

Question

我知道堆排序的空间复杂度是O(1)。但是对于一个递归程序，在计算空间复杂度时，它的深度--也就是它进行的递归调用的次数--也是计数的。因此，相同代码的迭代和递归方法的空间复杂度不同。那么，递归处理堆排序的空间复杂度是多少呢？

Answer 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函数首先将数组转换为堆，然后用减小的堆对数组进行排序。

需要注意的是，递归模式可以归结为尾递归。根据语言功能的不同，可以不使用调用堆栈(每次递归调用都会增加所使用的空间)来执行这一操作。

因此，除非递归算法还定义了如何实现递归调用--可能不包括尾部递归机制--否则它仍然可以用O(1)空间实现。

但是，如果不使用尾递归，则应考虑递归深度。这个深度最多是(堆)树的深度，它是logn。

Answer 2

您是对的，只有当您迭代执行heapify操作时，才是O(1)。

在类似于这里解释的HeapSort的递归方法的情况下，内存复杂度变成O(log )。

递归函数的内存复杂度是通过将递归调用的深度乘以单个调用的内存复杂度来计算的，在本例中，深度为O(log )，单个调用为O(1)。