[HaBo]

Aufruf aus dem Hauptprogramm:

der Algorithmus selbst:
Hauptziel war, eine bessere Best/AverageCase Laufzeit zu erhalten, als m*n?/2 , die man sonst mit einer Tabelle zustande bekommt.

Man stelle sich das ganze als eine Ansammlung von Mengen vor:
Menge Kind enthält {PC,Lego,PS}

Kind2={Fahrrad,Lego,rc-car}
usw.

Natürlich geht es auch andersherum:

playstation={ robert,marcus,stefan}
lego={robert,marcus,stefan,michael}
rc-car={stefan,michael}
computer={ robert,michael}

Gesucht sind nun zwei Mengen, die am meisten gemeinsame Elemente haben - deren
Schnittmenge (alle Elemente, die sowohl in Menge1 wie auch Menge2 vorkommen) also die größte Mächtigkeit hat.

Wenn man die gegebenen Mengen nun nach Mächtigkeit sortiert:

lego={robert,marcus,stefan,michael}
playstation={ robert,marcus,stefan}
rc-car={stefan,michael}
computer={ robert,michael}

kann man sie der Reihe nach durchgehen:
(starte mit der ersten Menge)
1.betrachte die aktuelle Menge und gehe der Reihe nach die anderen Mengen durch, ermittele dabei jeweils mit der aktuellen Menge gemeinsame Elemente (also den Schnitt).
Ist die Kardinalität (Mächtigkeit) der bisher größten ermittelten Schnittmenge >=der Mächtigkeit der nächsten zu betrachtenden Menge, brich die Betrachtung ab (Grund: da diese Mengen schon nach ihre Mächtigkeit sortiert sind, macht es keinen Sinn, sie alle durchzugehen, da sie dann weniger/gleichviele Elemente enthalten und wir somit auch keinen größeren Durchschnitt als den aktuellen finden werden).

2. gehe von der aktuellen zu der nächsten Menge. Hat diese weniger oder gleich viele Elemente, wie bereits im Schritt 1. gefundener Schnitt , sind wir fertig. Ansonsten gehe zu 1.


Bsp: start: lego-Menge:

1.lego+playstation haben 3 Elemente gemeinsam, die nächste Menge wäre
rc-car, diese hat aber nur 2 Elemente , also weiter mit Schritt 2
2.gehe zu Playstation, diese hat 3 Elemente. Wir haben breits einen Schnitt mit 3 Elementen - besser wird es nicht, daher sind wir fertig.

Wobei: das Ermitteln, ob ein Element auch in einer anderen Menge vorhanden ist, funktioniert in konstanter Zeit (es werden letzendlich HashSets->HashTables genutzt).
Dabei wird immer die kleineste Menge ausgewählt und überprüft, ob deren Elemente in der anderen Menge vorhanden sind. Aufwand der Schnittmengenbildung ist also = der Anzahl der Elemente in der kleineren Menge.