如何计算递归函数的空间复杂度 [英] How to calculate space complexity for a recursive function

问题描述

我知道堆的空间复杂度将其排序为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屋！