Po dwóch s można po prostu powtórzyć oba zestawy jednocześnie i porównać elementy, co powoduje liniową złożoność. To nie działa dla std::unordered_set s, ponieważ elementy mogą być przechowywane w dowolnej kolejności. Więc jak droga jest a == b dla std::unordered_set?Jak kosztowne jest porównywanie dwóch nieuporządkowanych zestawów dla równości?
Złożoność operator== i operator!=:
złożoność liniowa przeciętnego przypadku. N w najgorszym przypadku, gdzie N jest wielkością pojemnika.
Więcej szczegółów w standardowym §23.2.5, punkt 11:
Dla unordered_set i unordered_map złożoność operator== (czyli liczba połączeń do operatora == z value_type do orzecznika zwróconej przez key_equal() oraz do Hasher zwrócony przez hash_function()) jest proporcjonalna do N przeciętnego przypadku i N w najgorszym przypadku, w którym N jest a.size().
Najgorszym przypadkiem jest O (n²).
Ale nieuporządkowane zestawy są w rzeczywistości uporządkowane według wartości mieszania. Można więc porównywać hasze (jeśli to się nie powiedzie, zestawy nie mogą być równe), a następnie sprawdzić, czy te same skróty (liniowe) mają rzeczywiste te same wartości (O (n²) dla różnych wartości z tym samym skrótem) z tyłu.
W najlepszym wypadku jest to O (n).
Zwykle złożoność ma tendencję do O (n), jeśli funkcja hash jest "dobra" (różne obiekty -> zawsze różne hash) i do O (n²), jeśli funkcja hash jest "zła" (wszystko zawsze ma to samo wartość mieszania)
"Funkcja hash jest dobra (różne obiekty -> zawsze różne hash)" -> różne skróty mogą być prawdziwe nawet w przypadku strasznego algorytmu skrótu (np. Łańcuchy mieszające zawierające do 128 znaków, zwracając wartość skrótu 8 * 128-bitowego sklonowaną z ciąg), ale zmień go na liczbę segmentów, a wynik jest brzydki. Kiedy nie ma specjalnego wglądu w dane wejściowe, które ułatwiają unikanie kolizji, dobra funkcja hashowania po modyfikacji generalnie ma kolizje w stosunku do używanych do nieużywanych segmentów ... co nadal daje średnią O (n). –
@TonyDelroy: Dziękujemy za zwrócenie uwagi! "Dobry hasz" musi nie tylko zwracać "różne wartości", ale także "dobrze rozproszony" w odniesieniu do kubełków (obszar mieszania powinien być jednolity i główny szacunek dla wiader, aby zminimalizować efekt, o którym wspomniałeś) –
Czy masz sprawny sposób sprawdzenia przypisania członkostwa (na przykład czy są one wspierane przez hashtables)? – Thilo
W przejrzysty, prosty, łatwy do zrozumienia i zrozumienia wyraz standardu C++: "Dwa nieuporządkowane pojemniki' a' i 'b' są równe jeśli' a.size() == b.size() 'i, dla każdego odpowiednik-grupa kluczowa "[Ea1, Ea2]" uzyskana z 'a.equal_range (Ea1)' istnieje odpowiednik-grupa kluczy '[Eb1, Eb2)' uzyskana z 'b.equal_range (Ea1)', taka że ' odległość (Ea1, Ea2) == odległość (Eb1, Eb2) 'i' is_permutation (Ea1, Ea2, Eb1) 'zwraca' true'. Dla 'unordered_set' ... złożoność' operatora == '... jest proporcjonalnie do 'N' w przeciętnym przypadku i do' N^2' w najgorszym przypadku, gdzie 'N' to' a.size() '." –