为什么堆排序的空间复杂性是O（1）？
我不明白堆排序的空间复杂度是如何O（1）？ 尽管快速排序不使用任何额外的数组（即就地），但在最坏的情况下其空间复杂度为O（n），最佳情况下为O（lg n），因为堆栈在后端用于递归调用。 我对吗？
堆排序也是一样。 虽然它在原地，但是由于Build-Heap函数调用Max-Heapify函数，所以它的空间复杂度应该等于Max-Heapify，即O（lg n）。 不是吗？ 此外，Max-Heapify函数稍后将在根节点调用n次，正如我所说Max-Heapify（）空间复杂度为O（lg n）。
所以，堆排序的整体空间复杂度应该是O（lg n）。 但是我发现它在维基百科上是O（1）。 帮助我理解它。
Heapsort不会占用任何依赖于被排序数组大小的空间，只是数组本身的空间以及一些变量。 显然O（1）。
Quicksort跟踪一堆需要排序的子数组。 如果你聪明并且任何两个子数组都将较大的那个放在堆栈上，并立即对较小的那个进行排序，则需要O（log n）。
在实践中，它没有任何区别。
空间复杂度是指算法使用的额外空间。 堆排序不使用任何额外的空间（在O（n）），除了要排序的数组。 因此它是O（1）
有heapify的非递归版本（请参阅下面的示例）。 对于快速排序，如果仅在较小的分区上使用递归，然后循环返回以将什么是较大的分区拆分为2（再次使用这些2个分区中较小的那个上的递归等），则最大堆栈空间为O（log（ n）），但最坏的情况下仍然是O（n ^ 2）。
非递归heapify的非递归堆排序的C ++示例：
typedef unsigned int uint32_t;
void HeapSort(uint32_t *, size_t);
void Heapify(uint32_t *, size_t);
void SiftDown(uint32_t *, size_t, size_t);
void HeapSort(uint32_t * a, size_t count)
{
size_t end;
Heapify(a, count); // create initial heap
end = count-1;
while(end > 0){
// swap root (largest value) with end
std::swap(a[0], a[end]);
// reduce size of heap and
// increase size of sorted array
end--;
// repair the reduced heap
SiftDown(a, 0, end);
}
}
// create initial heap: for root = (count-2)/2 -> 0
// parent = root, children = root*2+1, root*2+2
// swap so that all a[parent] > a[child]
void Heapify(uint32_t * a, size_t count)
{
size_t root;
if(count < 2)
return;
// create sub-heaps of increasing size,
// with root going from (count-2)/2 to 0
root = (count - 2) / 2;
while(1){
SiftDown(a, root, count-1);
if(root == 0)
break;
root--;
}
}
// scan from root to end, swapping as needed to repair or create heap
void SiftDown(uint32_t * a, size_t root, size_t end){
size_t parent;
size_t child;
// while at least two children
for(parent = root; (child = parent * 2 + 2) <= end; ){
// choose the larger child
if(a[child-1] > a[child])
child = child-1;
// if child > parent then swap, parent = child
if(a[child] > a[parent]){
std::swap(a[child], a[parent]);
parent = child;
// else done with search for swaps
} else {
break;
}
}
// check for final only child
if((child = parent * 2 + 1) <= end)
if(a[child] > a[parent])
std::swap(a[child], a[parent]);
}
上一篇: Why space complexity of heap sort is O(1)?
下一篇: Difference in Space Complexity of different sorting algorithms