Ich habe zwei alphabetisch geordnete Listen
von Worten (Text-Arrays). Nun will ich die Schnittmenge,
d.h. alle Worte, die in beiden Listen auftreten
finden.
Einfachste Methode: alle Paare von Liste1 und
Liste2 durchprobieren–> Komplexitaet O(N*M)
Logarithmische Suche aller Elemente der kleineren
in der größeren Liste --> O(min(N,M)*log(max(N,M))
Der Reihe nach von a anfangend je einen Pointer
auf Liste 1 und 2 verschieben, bei übereinstimmung beide,
ansonsten den mit der niedrigeren „Ordnung“
–> O(N+M)
Gibts hierfür noch was schnelleres?
Gibts einen Algorithmus, bei dem man ausnutzen kann,
dass die Listen meistens „fast gleich“ sind?
Gibts einen Algorithmus, bei dem man ausnutzen kann,
dass man zwei zu dem aktuellen Problem sehr ähnliche
Listen schon überprüft hat?
Hallo,
ich halte 3. für optimal. Sicher kann man eine Kombination aus 2. & 3. verwenden, um schneller vorwärts zu springen (dabei müßte die binäre Suche die Position bestimmen, wo sich das ordnungsmäßig größere Element in der Liste mit dem ordnungsmäßig kleineren Element finden würde) aber bei starker Listenähnlichkeit bringt das nichts.
Hi,
O(m+n) ist minimum, denn du musst ja jedes Element jeder Liste
mindestens einmal anschauen (zumindest bei allgemeinen
Listen)…
Wenn ich als Zusatzinformation hätte, dass
in einer von beiden Listen nur ein Element
hinzugekommen oder weggefallen ist, dann
habe ich nur noch O(log(n)+log(m)).
Ist beides gleichzeitig möglich, so habe
ich keine Idee auf unter O(n+m) zu kommen…