如何计算堆排序的 space 复杂度

Question

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

Answer 1

你是对的，它是 O(1) 只有当你迭代地进行 heapify 操作时。

如果使用类似于此处解释的递归方法 HeapSort，内存复杂度变为 O(log N)。

递归函数的内存复杂度是通过将递归调用的深度乘以单次调用的内存复杂度来计算的，在我们的例子中，深度是 O(log N)，单次调用是 O(1 )

Answer 2

当使用递归实现 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。根据语言功能，这可以在不使用调用堆栈的情况下执行（其中使用的 space 随着每次递归调用而增加）。

所以除非递归算法也定义了如何应该实现递归调用"under the hood"——可能排除尾递归机制——，它仍然可以用 O(1) space.

来实现

如果不使用尾递归，则应考虑递归深度。该深度最多为（堆）树的深度，即logn.

如何计算堆排序的 space 复杂度

How to calculate space complexity for heapsort

algorithm

heapsort

data-structures