Listen vergleichen

Computer: Software & Programmierung Programmierung allgemein
#1

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.

  1. Einfachste Methode: alle Paare von Liste1 und
    Liste2 durchprobieren–> Komplexitaet O(N*M)
  2. Logarithmische Suche aller Elemente der kleineren
    in der größeren Liste --> O(min(N,M)*log(max(N,M))
  3. 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?

Gruss, Marco

#2

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.

Gruss
Enno

#3

O(m+n) ist minimum
Hi,
O(m+n) ist minimum, denn du musst ja jedes Element jeder Liste mindestens einmal anschauen (zumindest bei allgemeinen Listen)…

#4

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…

#5

Komisch , ich habe einen Antwortartikel geschrieben , aber irgendwie ist er verloren .
Mail mich mal an .