Heapsort。如何模拟最坏情况？

我很清楚如何对它进行编程，但我并不确定这个定义，例如如何用数学术语写下来。一个正常的heapsort在O表示法中用N个元素完成。所以O（日志（n））我刚开始heapsort，所以我可能会有点偏离这里。但是我怎么能找到一个随机元素，当有N个元素？然后选择该随机元素并删除它？我在想，在最坏的情况下 - 它必须穿过整棵树（因为元素可能在第一个地方或最后一个地方，例如最高或最低）。但是我怎样才能用数学术语写下来呢？Heapsort。如何模拟最坏情况？

来源

2012-10-28 XCoderX

您想为堆排序数学专门定义最坏的情况下？我不认为最终结果会是非常数学的。更像元元代码/数学/文本。并且Big-O表示法用大写字母O表示，而不是0. – keyser

对不起，我的英语有点不稳定。然而，我提出了log（2（n）），因为在最坏的情况下，我们正在寻找的随机元素是在树的底部，每个下一个分支都有两个额外的元素） - 我希望我的意思很清楚。 – XCoderX

哦，你想在大O的答案？ heapsort的最坏情况是O（n log n） – keyser

Heapsort的最坏情况下的性能是O（n log n）的，并且引用alestanis：在最大堆

最大：O（1）。最小分钟：O（1）。 O（n）中的相反情况。

Here是一个SO-answer解释如何在O（1）中执行相反的情况，如果您自己创建堆。

来源

2012-10-28 22:31:22 keyser

要建立maxheap阵列在最坏情况是O（n），并在最坏的情况下最大heapify complexcity是O（LOGN），所以堆排序在最坏情况是O（nlogn）

来源

2014-06-21 11:08:45 Sazib

Heapsort。如何模拟最坏情况？

回答

相关问题