Aufgabe:
(Original Aufgabentext ist in Englisch und relativ weit ausgeführt, ich beschränke mich hier also nur auf die relevanten Details)
- Gegeben sind zwei endliche Mengen A und B als Teilmengen der Menge der komplexen Zahlen
- Beide haben Größe n, sind also gleich groß
- Ordnen der Mengen ist nicht möglich, denn es besteht nur die Möglichkeit zwei Zahlen direkt zu vergleichen mit "=" (explizit kein <, >, ≤ und ≥)
- Hashing-Ansätze sind auch nicht möglich
- Es stehen jedoch die arithmetischen Operationen +, -, *, / und Wurzel zur Verfügung (jeweils auf die Elemente der Menge bezogen, also nicht als Mengenoperation)
- Alle Operationen haben Einheitskosten
Problem:
Es soll gezeigt werden, dass in O(n log2 n) Zeit...
(a) ...getestet werden kann, ob A und B disjunkt sind (A ∩ B = ∅).
(b) ...getestet werden kann, ob A eine Teilmenge von B ist (A ⊂ B).
(c) ... die Konjunktion der beiden Mengen berechnet werden kann (A ∩ B).
(d) ... die Disjunktion der beiden Mengen berechnet werden kann (A ∪ B).
Ansatz:
O(n log2 n) Zeit heißt, dass der Test, ob z.B. ein Element (eine beliebige Zahl) auch Teil der anderen Menge ist genau O(log2 n) Zeit braucht.
Nun ist aber mein Problem, dass mir nicht ersichtlich ist, wie dies funktionieren kann, zumindest auf die Menge der reellen Zahlen bezogen.
Ich weiß nun aber nicht inwieweit die ganze Geschichte sich ändert, wenn man die Eigenschaften komplexer Zahlen in Erwägung zieht und vermute die Lösung hier zu finden.
Auffällig ist mir hierbei, dass die Wurzel als Teil der arithmetischen Operationen zur Verfügung steht, bin nun aber überfragt in diesem Zusammenhang, wie ich nun die Elemente einfach vergleichen kann.
Zu mehr Ansätzen bin ich leider in den letzten Tagen nicht gekommen, denn ich zerbreche mir den Kopf nun schon einige Zeit mit dieser Aufgabe.
Ich hoffe ihr könnt mir weiterhelfen. Jeder Antwort, oder Anregung ist mir sehr hilfreich.
