堆排序的递归关系是什么？

Question

我需要用Master's Theorem计算Heap Sort的时间复杂度，但我不知道哪个是递归关系。我知道它的复杂度是 O(n log n)，因为它遍历了 n 次二叉树。但是我需要专门使用 Master's Theorem，为此我需要递推关系。堆排序的关系是什么？

Answer 1

让我们从堆排序算法开始：

heap_sort(int Arr[])
{
    int heap_size = n;

    build_maxheap(Arr);
    for(int i = n; i >= 2 ; i--)
    {
        swap(Arr[1], Arr[i]);
        heap_size = heap_size - 1;
        heapify(Arr, 1, heap_size);
    }
}

build_maxheap() 函数具有 O(n) 的标准实现。

排序的重要部分是for循环，它执行了n次。在其中我们有一个 swap 方法调用和 heapify 方法调用。 heapify 方法是完全二叉树的标准遍历。因此，复杂度为 O(log n)

T(n) = O(n) + n * O(log n) = O(n * log n)

大师定理对于解决许多分而治之算法的递归关系很有用。

现在，如果您对掌握定理的应用感兴趣。我们可以实现一个递归算法

heap_sort(int Arr[])
{
    int heap_size = n;
    build_maxheap(Arr);

    heap_sort_recurse(Arr, heap_size);

}

heap_sort_recurse(int Arr[], heap_size)
{
    swap(Arr[1], Arr[n]);
    heap_size = heap_size - 1;
    heapify(Arr, 1, heap_size);
}

在这种情况下，您可能有如下的递归方程

T(n) = T(n-1) + O(log n)

显然，这不能直接用主定理来解决。有一个为减法和征服类型派生的修改公式。

这个link可能会有用。

对于表格的重复，

T(n) = aT(n-b) + f(n)

where n > 1, a>0, b>0

如果f(n)为O(n^k)且k>=0，则

如果 a<1 则 T(n) = O(n^k)
如果 a=1 则 T(n) = O(n^k+1)
如果 a>1 则 T(n) = O(n^k * a^n/b)

应用这个，

我们有 a = 1, b = 1, k = 0

因此，第二种情况适用。因此，

T(n) = O(n⁰⁺¹ * log n) = O(n * log n)

希望对您有所帮助！

堆排序的递归关系是什么？

What is Heap Sort's recurrence relation?

algorithm

sorting

time-complexity

heapsort