我忙着准备考试，只是在做一些旧试卷。下面的问题是我似乎做不到的唯一一个问题(我真的不知道从哪里开始)。任何帮助将不胜感激。
使用 Ω(nlogn) 比较排序边界、自底向上堆构造的 theta(n) 边界和插入排序的顺序复杂度来表明堆中最坏情况的反转次数是 Ω(nlogn)。
最佳答案
插入排序的复杂度为 O(n+d)，其中 d 是反转对的数量。
现在假设你有一组数字，你堆化 (Theta(n)) 然后对它们执行插入排序。它对堆数组中最坏情况下的反转对数有什么看法？
关于algorithm - 如何证明堆中最坏情况的反转次数是Ω(nlogn)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3007254/