2

证明当一个大小为 n 的数组 A 有 O(n) 求逆时，它可以在 Θ(n) 中排序。

我不知道这个问题到底在问什么。我最好的猜测是我们对预排序的输入使用插入排序，这样我们可以通过排序来实现 Θ(n) 复杂度。这就是问题要问我的吗？

4

1 回答 1

3

作为提示 - 插入排序的运行时间是 Θ(n + I)，其中 n 是元素数，I 是数组中的反转数。如果对数组进行插入排序会发生什么，因为它只有 O(n) 反转？时间复杂度是多少？

希望这可以帮助！

于 2013-10-29T06:21:25.080 回答