二進制搜索未排序數組的時間複雜度

我被兩個時間的複雜性困住了。使用排序數組進行二分搜索是O（logN）。所以要搜索一個未排序的數組，我們必須首先對它進行排序，以便變成O（NlogN）。那麼我們可以執行二進制搜索，其複雜度爲O（N），但我已經讀過它可能是O（NlogN）。哪個是對的？二進制搜索未排序數組的時間複雜度

來源

2013-04-09 user1521306

這些是兩個獨立的操作。無論如何，二分查找總是** O（log n）**。 – squiguy 2013-04-09 21:35:21

確實，二進制搜索不適用於未排序的數組;但是，您首先必須對數組進行排序以執行二分搜索。至少這是我最近學到的。 – user2373448 2017-11-21 21:16:36

二進制搜索用於「排序」列表。複雜度是O（logn）。

二進制搜索不適用於「未排序」列表。對於這些列表，只需從第一個元素開始直接搜索;這給出了O（n）的複雜度。如果要使用MergeSort或任何其他O（nlogn）算法對數組進行排序，則複雜度將爲O（nlogn）。

O（LOGN）< O（n）的< O（nlogn）

來源

2013-04-09 21:31:55 LuiNova

即使數組有點小但未排序，BinarySearch仍然可以工作。好注意。 – ofarooq 2016-12-27 18:21:34

回答你的問題是你的問題本身。您首先對列表進行排序。如果使用快速排序或合併排序對列表進行排序，則複雜度將變爲o（n log n）。第一部分結束。執行二進制搜索的第二部分是在「分類列表」上完成的。二進制搜索的複雜度是o（log n）。因此，最終程序的複雜性仍然是o（n日誌n）n（n =）。但是，如果您想計算數組的中位數，則不必對列表進行排序。線性或順序搜索的簡單應用可以幫助您。

來源

2013-12-02 18:19:03 yuvrajm

線性搜索的時間複雜度爲O(n)，二分查找的時間複雜度爲O(log n)（對數基數爲2）。如果我們有一個未排序的數組，並且想要使用二進制搜索，我們必須首先對數組進行排序。在這裏，我們必須花費時間O(n logn)對數組進行排序，然後花時間搜索元素。

來源

2016-11-19 06:37:31

二進制搜索未排序數組的時間複雜度

回答

相關問題