Finden Sie Elemente, die sich in mindestens

11

Betrachten Sie Wertesätze (dargestellt als sortierte Arrays ohne Duplikate und mit einer bekannten Größe (dh die Größe kann in O (1) erhalten werden). Die Werte können in O (1) -Zeit auf Gleichheit getestet werden. Ich möchte um den Satz von Werten zu erhalten, die in mindestens k verschiedenen Sätzen unter den n vorhanden sind .nkn

Der naheliegende Algorithmus, um dies zu tun, besteht darin, alle Mengen durchzugehen, die Anzahl der Vorkommen jedes Werts zu zählen und diejenigen mit einer höheren Anzahl als . In einigen Fällen können Sie es jedoch besser machen: Wenn beispielsweise n = k = 2 ist und eine Menge S 1 viel kleiner als die andere Menge S 2 ist , ist es effizienter, alle Elemente von S 1 zu betrachten und auszuführen eine binäre Suche für jeden von ihnen in S 2 : Der Ansatz der binären Suche kostet O ( | S 1 | log ( | S 2 |)kn=k=2S1S2S1S2 während der naive Ansatz O ( | S 1 | + | S 2 | ) kostet,was schlimmer ist, wenn | S 1 | < < | S 2 | .O(|S1|log⁡(|S2|))O(|S1|+|S2|)|S1|<<|S2|

In welchen Situationen können wir in diesem Sinne besser abschneiden als mit dem naiven Algorithmus? (Wenn dies ein bekanntes Problem ist, würde ich mich freuen, den üblichen Namen zu kennen und Referenzen zu haben.)

ds.algorithms a3nm
quelle
3
Dies fällt unter die allgemeine Kategorie "Top-K" -Ergebnisse oder "Heavy Hitter". Letzteres ist näher an dem, was Sie suchen. Die meisten Arbeiten in diesem Bereich konzentrieren sich jedoch auf große Datenmengen und sublineare Speicherbeschränkungen.
Suresh Venkat
9
O(|S1|log⁡(|S2|/|S1|))

Antworten:

2

Tk

S2

a3nm
quelle
1

Ihr Problem ähnelt dem Data Mining-Problem beim Auffinden häufiger Objektgruppen , das auch als Lernen von Assoziationsregeln bezeichnet wird . Wenn ich es richtig verstanden habe, kann Ihr Problem darauf reduziert werden, häufige Elemente der Kardinalität 1 (dh Singletons) mit Unterstützung > = k zu finden . Natürlich ermöglichen die verfügbaren Algorithmen (wie Apriori, Eclat, D-CLUB usw.) für das Problem auch die Bestimmung häufiger Kardinalitätselemente> 1.

Massimo Cafaro
quelle