代码之家 › 专栏 › 技术社区 › user2798432

我们能用heapsort在线性时间内对一组无序的数字进行排序吗?

heapsort big-o algorithm performance

user2798432 · 技术社区 · 12 年前

嘿,伙计们,快提问。。

正如我们所知,我们可以在线性时间内从一组无序的数字中构建一个堆。有人能证明是怎么做到的吗?

提前感谢!

1 回复 | 直到 12 年前

Drew Hall 12 年前

不

尽管您可以在线性(O(n))时间内构建一个堆(可能实现为一个完整的二叉树),但每次从堆中提取都需要O(log(n)时间,以保持堆不变。因此,从二进制堆组装排序后的数组总共需要O(n-log(n))时间,就像所有基于二进制比较的最优排序算法一样。

推荐文章

Sweepy Dodo · JSON lite的格式化

1 年前

Merlin Nestler · 为什么索引中的列顺序在这种情况下会产生如此大的影响?

1 年前

giantjenga · 优化整数向量到二进制向量的转换

1 年前

Adriaantje · Powershell版本的cut-d在处理大文件时速度很慢,我是否错过了快速的方法?

1 年前

Costinean Sebastian · 如何优化使用for循环处理大型数组的MATLAB脚本的执行时间?"

1 年前

Zegarek · Postgresql递归查询未提供预期结果

1 年前

Joe · 为什么这两个查询之间的性能存在如此大的差异?

1 年前

tic-toc-choc · 在`dplyr中高效使用列表进行过滤`

1 年前

Mohan · 是否有一种更快的方法来编写代码,从1:N中提取许多随机样本?

1 年前

user2980746 · 在C#字典中键入xyz对的最有效方法是什么?

1 年前