在排序的std :: list中搜索的複雜性是什麼？

在排序的std :: list中搜索的複雜性是什麼？我知道如果數據結構具有隨機訪問，那麼在排序數據中搜索的複雜度就是O（log n）。但是因爲列表沒有隨機訪問，所以排序時它的複雜性是什麼？在排序的std :: list中搜索的複雜性是什麼？

來源

2014-10-02 user3852441

@dyp按值搜索的複雜性 – user3852441 2014-10-02 22:44:03

請注意，除了搜索的複雜性之外，應該避免（鏈接）列表，除非您知道它們在特定情況下的性能優於矢量/數組（這些情況非常罕見）。 C++發明家Bjarne Stroustrup關於該主題的有趣討論：https://www.youtube.com/watch?v=YQs6IC-vgmo – leemes 2014-10-02 23:14:51

嗯，這是O（N）。搜索總是O（N）在std::list，排序與否。

排序集合的幫助，因爲你可以知道，如果你太遠，或不夠。但是既然你不能從任何地方開始，但只能在列表的一端，這無濟於事。

來源

2014-10-02 22:40:10 Quentin

感謝你的repy.That即使二元搜索也無助於std :: list已分類？ – user3852441 2014-10-02 22:48:13

是的。一旦你在列表的中間，你知道你應該左轉還是右轉，但是你已經花了O（N）時間通過鏈接到達那裏。 – Quentin 2014-10-02 22:50:20

列表是雙鏈表，它在每個節點中都有指向前/後的兩個指針。即使你知道節點在中間，你仍然需要經過每個下一個指針才能到達中間。但是，如果使用矢量，它具有隨機存儲器訪問權限，則可以跳轉到中間節點。 – billz 2014-10-02 23:10:21

這取決於你如何搜索。鑑於std::list<T> x和值v不在列表中，

std::find(x.begin(), x.end(), value)是線性搜索，因此將需要x.size()比較和迭代步驟，
std::binary_search(x.begin(), x.end())執行與O（日誌二進制搜索（x.size()））比較，但它仍然必須線性遞增迭代器以解決每個比較的目標（並且對於std::lower_bound等）。如果列表不是按排序順序，則此行爲對於此調用未定義。

通常，迭代器遞增對於基於節點的容器具有不平凡的開銷，因爲它涉及指針追蹤並且在內存中是非本地的。但是，您需要考慮值類型的比較操作的成本（可能很高，例如很長，幾乎相等的字符串）。此外，您可以通過從專用場所分配節點來解決內存局部性問題。

來源

2014-10-02 22:41:24

「這取決於你如何搜索」 - 不，你甚至可以在你的答案中解釋爲什麼它在每種情況下都是線性時間... – leemes 2014-10-02 22:46:41

@leemes：正如我在我的回答中解釋的那樣，「它」有點兒複雜。 – 2014-10-02 22:47:53

他問複雜性，這是一個簡單的答案：O（n）。你解釋的是*成本*，而不是*複雜性*。當然，解釋仍然很有幫助。 – leemes 2014-10-02 22:48:41

在排序的std :: list中搜索的複雜性是什麼？

回答

相關問題