如何证明堆中最坏情况的反转次数是 Ω(nlogn)？
我正忙着准备考试，只是做一些旧的试卷。下面的问题是我似乎无法做的唯一一个问题（我真的不知道从哪里开始）。任何帮助将不胜感激。
使用 Ω(nlogn) 比较排序界限、自底向上堆构造的 theta(n) 界限以及插入排序的顺序复杂度来表明堆中最坏情况的反转次数为 Ω(nlogn)。
I am busy preparing for exams, just doing some old exam papers. The question below is the only one I can't seem to do (I don't really know where to start). Any help would be appreciated greatly.
Use the Ω(nlogn) comparison sort bound, the theta(n) bound for bottom-up heap construction, and the order complexity of insertion sort to show that the worst-case number of inversions in a heap is Ω(nlogn).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
插入排序的复杂度为 O(n+d)，其中 d 是反转对的数量。
现在假设您有一组数字，您将其堆起来 (Theta(n))，然后对它们执行插入排序。堆数组中最坏情况下的反转对数量说明了什么？
The complexity of insertion sort is O(n+d) where d is the number of inversion pairs.
Now say you had a set of numbers, which you heapify (Theta(n)) and then perform insertion sort on them. What does it say about the worst case number of inversion pairs in the heap array?