算法比較在未排序的陣列

如果我有一個排序的數組A [1 ..... N]使用線性搜索用冒泡排序來對數組進行排序，以搜尋數x算法比較在未排序的陣列

哪種方式更有效率 - 1或2？

如何自圓其說呢？

2014-04-28 Amanda_Q

什麼是線性搜索的複雜性？什麼是泡沫排序的複雜性？二分查找的複雜度是多少？你要做多少次搜索？爲什麼不使用更快的排序？這將如何改變答案？ N有多大？ Big-O符號用於N∞∞的漸近行爲;如果N很小，餘額可能會改變。 –

如果您需要尋找一個單一的數字，沒有什麼可以打敗線性搜索：分類無法進行比O（n）的速度更快，甚至只有在特殊情況下是可以實現的。另外，冒泡排序是極其低效的，取爲O（n 2 ）時間。二進制搜索比快，所以總體定時將是由爲O（n 2 ）所支配。

因此您比較爲O（n）至O（N 2 ）;顯然，O（n）勝。

如果您需要搜索k不同的數字，其中k大於n 。這種比較的結果很可能是負面的。

2014-04-28 01:41:22 dasblinkenlight

基數排序是否更有效地對數組進行排序？ –

@Amanda_Q：任何具有「O（nlogn）」複雜度的排序都是有效的。只需選擇一個。如果你不確定選擇'quicksort' – arunmoezhi

@Amanda_Q基數排序是一種給予OO（n）性能的類型。 – dasblinkenlight

回答