rak*_*esh 5 sorting algorithm heap
我们可以说,当大小为n的数组A中的所有元素相同时,堆排序的运行时间为O(n)
- >如果是这种情况,是否是O(n)最好的案例运行时间的heapsort
当所有元素相等时,构建堆需要O(n)步.因为当一个元素在比较O(1)之后被添加到堆中时,我们看到它处于正确的位置.
删除根也是O(1),当我们交换尾部和根时,仍然满足堆属性.
所有元素都以O(n)的形式添加到堆中,并在O(n)中删除.所以,是的,在这种情况下,heapsort是O(n).我想不出一个更好的案例,所以最好的案例必须是O(n).
'Heapsorts最好的情况是O(n)'在英语中意味着:存在大小为n的数组,这样heapsort最多需要k*n比较它.这在理论上很好,但在实践中并没有说明heapsort的好或快.