递归构建堆的空间复杂度

Question

我正在尝试解决Build-Heap递归形式的空间复杂性。这就是我到目前为止所做的，我想知道我的错误在哪里(如果有)：

首先: Build-Heap是由for循环构成的，其时间复杂度为Theta(n)。

Build-Heap调用Heapify-Down Theta(n)次-(由于Build-Heap时间复杂性)，所以: Heapify-Down在每次i-递归调用时将n\i个元素的数组推送到空间堆栈，这意味着它使用Theta(logn)的空间复杂度。

结论:θ(N)*Theta(Logn)= Theta(nlogn)。

我不确定我对Heapify-Down被调用的次数的解释，而且我在互联网上发现Build-Heap空间复杂度实际上是Theta(logn)，这意味着我的结论是错误的。谢谢您的支持。

Answer 1

当它是堆排序时，您的结论是绝对正确的，因为对BUILD-MAX-HEAP的调用需要O(n)时间，而对MAX-HEAPIFY的n-1次调用中的每一次都需要O(.So n)时间，总运行时间将是O(nlogn)。

您可以参考Cormen，Leiserson和Rivest的introduction to algorithms获得详细的解释