堆排序的递归关系是什么?
What is Heap Sort's recurrence relation?
我需要用Master's Theorem计算Heap Sort的时间复杂度,但我不知道哪个是递归关系。我知道它的复杂度是 O(n log n),因为它遍历了 n 次二叉树。但是我需要专门使用 Master's Theorem,为此我需要递推关系。堆排序的关系是什么?
让我们从堆排序算法开始:
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(nk)且k>=0,则
- 如果 a<1 则 T(n) = O(nk)
- 如果 a=1 则 T(n) = O(nk+1)
- 如果 a>1 则 T(n) = O(nk * an/b)
应用这个,
我们有 a = 1, b = 1, k = 0
因此,第二种情况适用。因此,
T(n) = O(n0+1 * log n)
= O(n * log n)
希望对您有所帮助!
我需要用Master's Theorem计算Heap Sort的时间复杂度,但我不知道哪个是递归关系。我知道它的复杂度是 O(n log n),因为它遍历了 n 次二叉树。但是我需要专门使用 Master's Theorem,为此我需要递推关系。堆排序的关系是什么?
让我们从堆排序算法开始:
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(nk)且k>=0,则
- 如果 a<1 则 T(n) = O(nk)
- 如果 a=1 则 T(n) = O(nk+1)
- 如果 a>1 则 T(n) = O(nk * an/b)
应用这个,
我们有 a = 1, b = 1, k = 0
因此,第二种情况适用。因此,
T(n) = O(n0+1 * log n) = O(n * log n)
希望对您有所帮助!