Czy istnieje algorytm (najlepiej stały czas) do sprawdzenia, czy zbiór A jest podzbiorem zbioru B?Algorytm sprawdzania, czy zbiór A jest podzbiorem zbioru B w czasie szybszym niż czas liniowy
Tworzenie struktur danych ułatwiających ten problem nie jest wliczane do środowiska wykonawczego.
Cóż, będziesz musiał spojrzeć na każdy element A, więc musi to być co najmniej czas liniowy w rozmiarze A.
Algorytm O(A+B) jest łatwy dzięki hashtables (przechowywać elementy B w hashtable, a następnie sprawdzić każdy element z A). Nie sądzę, że możesz zrobić coś lepszego, jeśli nie znasz jakiejś zaawansowanej struktury dla B. Na przykład, jeśli B jest przechowywany w posortowanej kolejności, można wykonać O(A log B) przy użyciu wyszukiwania binarnego.
Jeśli posortujesz oba zestawy, możesz porównać nagłówek dwóch kolekcji. Wydajność tego algorytmu to O (A + B). – Miguel
Możesz przejść do filtr bloom (http://en.wikipedia.org/wiki/Bloom_filter). Jednak nie może być fałszywe alarmy, które mogą być rozwiązane metodą wspomnianej przez Keitha powyżej (należy jednak pamiętać, że w najgorszym przypadku złożoność mieszaja nie jest O (n), ale można to zrobić O (nlogn).
Podoba mi się ten algorytm, ponieważ wykonywanie niektórych operacji przetwarzania jest bardzo szybkie w moim przypadku. Filtr rozkwitu działałby na serwerze, a przetwarzanie końcowe po zestawie wyników działałoby po stronie klienta. – volni
Jeśli masz listę najsłabiej wspólnych liter i par liter w zestawie strun, można przechowuj swoje zestawy posortowane według najmniej popularnych liter i par liter i zwiększaj swoje szanse na odrzucenie negatywnych dopasowań tak szybko, jak to możliwe. 10 Nie jest dla mnie jasne, jak dobrze byłoby to połączyć z filtrem kwitnienia, Prawdopodobnie zrobi to stół mieszający, ponieważ nie ma zbyt wielu digramów i liter.
Jeśli masz jakieś informacje na temat maksymalnego rozmiaru podzbiorów lub nawet wspólnego rozmiaru, możesz podobnie wstępnie przygotować dane, umieszczając wszystkie podzbiory o danym rozmiarze w filtrze bloom, jak wspomniano.
Można również wykonać kombinację obu tych metod.
Znaleziono tę odpowiedź: http://stackoverflow.com/a/1338515/174674 – volni
Potrzebujemy więcej informacji o ustawionej zawartości. Ogólne algorytmy nie dają stałej złożoności czasu. Przynajmniej żaden nie znam. –
Ustawionymi elementami są łańcuchy, ale oczywiście możemy je uruchomić przez jakiś skrót lub przypisać mu pozycje w zestawie bitów, jeśli dałoby to szybszy algorytm. – volni