按Θ（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

回答