按Θ（n）复杂度对数组进行排序

证明当大小为n的数组A在O（n）反转时可以在Θ（n）中进行排序。按Θ（n）复杂度对数组进行排序

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

2013-10-29 dood

您能否重新说明您的问题......？ –

“我的猜测是我们在预分类输入上使用插入排序，这样我们就可以实现O（n）的复杂性”。那么，输入没有完全预先分类。（在这种情况下，不会有倒数。）根据这个问题，这里有O（n）个倒数。所以它可能类似于5,4,7,6,10,9。使用下面的提示并证明排序可以在\ theta（n）时间内发生。 – Shobit

@Shobit明白了，谢谢！ – dood

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

希望这会有所帮助！

2013-10-29 06:21:25 templatetypedef

在这种情况下，复杂度将是Θ（2n），它只是Θ（n）？ – dood

是的，这是正确的。 – Shobit

回答