堆排序的最坏运行时间和最优运行时间_heapsort的运行时间

作者：菜鸟追梦旅行 | 2024-06-18 07:30:19

踩

heapsort的运行时间

1964年Williams发明的，1992年Sedgewick发表了堆排序性能分析 "The analysis of heapsort"。

所以求堆排序的最优运行时间比较难。

一、最坏运行时间

由于前面已经证明了：在n个元素的堆中，MAX-HEAPIFY的最坏运行时间为 Ω(lgn)。

如果要求堆排序的最坏运行时间，则可以假设每次MAX-HEAPIFY都是最坏运行时间。

堆T为一般堆，即可能是满二叉树，也可能不是满二叉树，如果不是满二叉树，则将最下面一层删除后变成满二叉树，即为T‘。

设F()为最坏运行时间，则F(T)>=F(T').

我们只要求F(T')= Ω （nlgn）即可。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/734206