当我阅读归并排序的空间复杂度时,我得到的空间复杂度是O(n+logn)
。 O(logn)
是在我们考虑递归过程的堆栈帧大小时计算的。
但是heapsort也用到了递归过程,也就是heapify过程。为什么堆排序的空间复杂度是O(1)
?
我正在阅读的代码是
```java
public class HeapSort {
public void buildheap(int array[]){
int length = array.length;
int heapsize = length;
int nonleaf = length / 2 - 1;
for(int i = nonleaf; i>=0;i--){
heapify(array,i,heapsize);
}
}
public void heapify(int array[], int i,int heapsize){
int smallest = i;
int left = 2*i+1;
int right = 2*i+2;
if(left<heapsize){
if(array[i]>array[left]){
smallest = left;
}
else smallest = i;
}
if(right<heapsize){
if(array[smallest]>array[right]){
smallest = right;
}
}
if(smallest != i){
int temp;
temp = array[i];
array[i] = array[smallest];
array[smallest] = temp;
heapify(array,smallest,heapsize);
}
}
public void heapsort(int array[]){
int heapsize = array.length;
buildheap(array);
for(int i=0;i<array.length-1;i++){
// swap the first and the last
int temp;
temp = array[0];
array[0] = array[heapsize-1];
array[heapsize-1] = temp;
// heapify the array
heapsize = heapsize - 1;
heapify(array,0,heapsize);
}
}
```
最佳答案
您发布的 Java 代码的空间复杂度不是 O(1)
,因为它占用了非常量的堆栈空间。
然而,这不是实现堆排序的常用方法。 heapify
方法中的递归可以很容易地替换为简单的 while 循环(无需引入任何额外的数据结构,如堆栈)。如果这样做,它将在 O(1) 空间内运行。
关于algorithm - 为什么 heapsort 的空间复杂度是 `O(1)` 递归 heapify 过程?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29089595/