algorithm - 如何证明堆中最坏情况下的反转次数是Ω(nlogn)？

Question

我正忙着准备考试，只是在做一些旧的试卷。下面的问题是我似乎唯一做不到的问题(我真的不知道从哪里开始)。任何帮助将不胜感激。

使用 Ω(nlogn) 比较排序边界、theta(n) 边界用于自下而上的堆构造以及插入排序的顺序复杂度来表明堆中最坏情况下的倒置次数为 Ω(nlogn ).

Answer 1

插入排序的复杂度为 O(n+d) 其中 d 是反转对的数量。

现在假设您有一组数字，您将其堆化 (Theta(n))，然后对它们执行插入排序。堆数组中最坏情况下的反转对数是怎么说的？