Znaleźć przedmioty, które są w co najmniej

11

Rozważ zestawów wartości (reprezentowanych jako uporządkowane tablice bez duplikatów i ze znanym rozmiarem (tzn. Rozmiar można uzyskać w O (1)). Wartości można sprawdzić pod kątem równości w czasie O (1). Chcę aby otrzymać zestaw wartości, które są obecne w co najmniej różnych zestawach spośród .nkn

Oczywistym algorytmem do tego jest przejście przez wszystkie zestawy, policzenie liczby wystąpień każdej wartości i zwrócenie tych z liczbą większą niż . Jednak w niektórych przypadkach możesz zrobić lepiej: na przykład, gdy i gdy jeden zestaw jest znacznie mniejszy niż drugi zestaw , bardziej efektywnie jest spojrzeć na wszystkie elementykn=k=2S1S2 i wykonać binarny szukaj każdego z nich w S 2 : podejście do wyszukiwania binarnego kosztuje O ( | S 1 | log ( | S 2 | ) ), podczas gdy podejście naiwne kosztujeS1S2O(|S1|log⁡(|S2|)) co jest gorsze, gdy | S 1 | < < | S 2 | .O(|S1|+|S2|)|S1|<<|S2|

Mając to na uwadze, w jakich sytuacjach możemy zrobić coś lepszego niż naiwny algorytm? (Jeśli jest to dobrze znany problem, chętnie poznam jego zwykłą nazwę i referencje).

ds.algorithms a3nm
źródło
3
Obejmuje to ogólną kategorię wyników „top-K” lub „ciężkich uderzeń”. To drugie jest bliższe temu, czego szukasz. Większość prac w tej przestrzeni koncentruje się jednak na dużych zestawach danych i ograniczeniach pamięci sublinearnej.
Suresh Venkat
9
O(|S1|log⁡(|S2|/|S1|))

Odpowiedzi:

1

Twój problem jest podobny do problemu eksploracji danych polegającego na znajdowaniu częstych zestawów przedmiotów , znanym również jako uczenie się reguł asocjacyjnych . Jeśli dobrze zrozumiałem, twój problem może zostać zredukowany do znalezienia częstych zestawów przedmiotów liczności 1 (tj. Singletonów) z obsługą > = k . Oczywiście dostępne algorytmy (takie jak Apriori, Eclat, D-CLUB itp.) Dla problemu pozwalają również na określenie częstych zestawów liczności> 1.

Massimo Cafaro
źródło