假設存在包含未排序數據的數組，並且需要選擇線性搜索或二分搜索進行搜索。那麼我應該選擇哪個選項？線性搜索的時間複雜度爲O（n），二進制搜索的時間複雜度爲O（log n）。但是，最快的排序算法給出了O（n * log n）的時間複雜度。現在，我不知道如何「添加」兩種算法的複雜性（如果這是正確的話），因此，我正在問這個問題。排序完成之前的二進制搜索的時間複雜度...請參閱
所以我的問題是，如果排序然後二進制搜索比單純的線性搜索更好還是以其他方式？
另外，如何證明使用大O符號（我的意思是「添加」和「比較」時間複雜度）？
非常感謝您的閱讀！那意義重大。
你並不真正「增加」複雜性。正如你所說，排序是O（n * log n），搜索是O（log n）。如果你對他們做「正常的數學」，那麼它會是（n + 1）* log n，它仍然是n * log n。
當您執行這樣的多個步驟時，您通常會採取最高的複雜度並稱之爲。畢竟，當n足夠大時，n * log n會使log n變矮。
想想這樣：當n是1,000,000時，n * log n是2000萬。 log n是20.那麼20,000,000和20,000,020之間有什麼區別？ （log n）項無關緊要。所以（n log n）+（log n）對於所有意圖和目的都等於（n log n）。即使當n是100時，log n也是7.當n甚至是中等大時，（log n）項不會有什麼區別。
在你的特殊情況下，如果你只需要一次搜索列表，那麼順序搜索就是要走的路。如果您需要多次搜索，則必須將m次搜索的成本（m * n）與排序成本進行權衡，然後進行搜索。如果你對最短時間感興趣，並且知道你將搜索列表的次數，那麼如果（m * n）小於（n * log n），則使用順序搜索。否則使用排序然後二進制搜索。
但這不是唯一的考慮因素。在排序列表上進行二進制搜索會爲您提供非常快速的響應時間，而線性搜索對於單個項目可能需要很長時間。如果你可以在程序啓動時對列表進行排序，那麼這可能是最好的方法，因爲一旦程序運行，就會找到（或未找到）項目。對列表進行排序可爲您提供更好的響應時間。在啓動過程中支付分揀費用比在操作過程中遇到非常不可預測的響應時間更好。或者發現你需要進行比你想象的更多的搜索。 。 。
所以我的問題是，如果排序然後二進制搜索優於簡單的線性搜索
是的，你是對的。
當數組已被排序時，應該應用二進制搜索。否則，您不能使用二分查找。如果您有大量查詢，則最好先對數組進行排序，然後應用二進制搜索。但是，如果您只有幾個查詢，也許線性搜索就足夠了。
至於大O符號，它始終是「大」部分—即，如果你排序然後二進制搜索，它將是O（n * lgn）。如果你只是使用線性搜索，它是O（n）。但考慮到查詢次數（m）時，第一種方法是O（n * lgn + m * lgn），而第二種方法變爲O（m * n）。您可以看到，如果m很大（m = n或m >> n），則第二種方法比二元搜索更復雜。
謝謝！但是，我如何在數學上證明它？ – finitenessofinfinity 2013-02-11 01:49:37
如果您必須執行一次搜索，請執行線性搜索。這顯然比分類和二分搜索更好。
但是如果您有多個搜索查詢，那麼在大多數情況下，您應該先對數組進行排序，然後將二進制搜索應用於每個查詢。
爲什麼？假設您要執行O（k）搜索查詢。如果您進行線性搜索，您將以O（n * k）操作結束。如果你第一次排序，那將需要O（nlogn）+ O（klogn）= O（（n + k）logn）操作。什麼是更好的 ？當k很小（小於logn）時，最好進行線性搜索。但是在大多數情況下，你最好先排序。
感謝您的回答！ – Vikram 2013-11-05 17:16:00