algorithm - 堆排序。怎么可能模拟最坏情况？

Question

我对如何编程很清楚，但我不确定定义，例如如何用数学术语写下来。一个普通的堆排序是用 O 表示法中的 N 个元素完成的。所以 O(log(n)) 我刚开始使用堆排序，所以我可能有点偏离这里。但是，当有 N 个元素时，我如何寻找随机元素？然后选择那个随机元素并删除它？我在想，在最坏的情况下，它必须遍历整个树（因为元素可能位于第一位或最后一位，例如最高或最低）。但是我怎么能用数学术语把它写下来呢？

Answer 1

Heapsort的最坏情况性能是 O(n log n)，引用alestanis的话：

最大堆中的最大值：O(1)。最小堆中的最小值：O(1)。O(n) 中的相反情况。

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

Answer 2

构建最大堆数组最坏情况是 O(n) 并且在最坏情况下最大化堆复杂度是 O(logn) 所以 HeapSort 最坏情况是 O(nlogn)