Datenstruktur < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:16 Di 30.12.2008 | | Autor: | Tasel |
| Aufgabe | | Sei $ [mm] K_{1} [/mm] $ und sei $ [mm] K_{2} [/mm] $ eine Menge von Elementen. Die Operation VEREINIGEN soll diese beiden Mengen vereinigen und $ [mm] K_{1} [/mm] = [mm] K_{1} \cup K_{2} [/mm] $ wiedergeben. Verwenden Sie einen geeignete Datenstruktur, so dass die Operation in $ O(1) $ ausgeführt werden kann. (Gib die Operation VEREINIGUNG in Pseudocode an.) |
Hallo Forum!
Ich versuche schon seit einiger Zeit diese Aufgabe zu lösen. Jedoch schaffe ich bei all meinen Ansätzen nie eine Laufzeit von $ O(1) $ zu erreichen, sondern komme immer auf $ O(n) $. Dies liegt daran, dass ich bei all meinen Ansätzen irgendwann, mindestens einmal, alle Elemente von $ [mm] K_{1} [/mm] $ mit $ [mm] K_{2} [/mm] $ vergleiche. Ist es überhaupt möglich eine lineare Laufzeit hierfür zu erhalten? Irgendwie müsste ich hierfür ja wissen, welche Elemente beide Mengen enthalten ohne jemals eine von ihnen angeschaut zu haben ...
Irgendwie recht seltsam finde ich.
Schon jetzt danke für Eure Hilfe
Tasel
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Du darfst doch die Datenstruktur frei wählen, darauf zielt ja auch Deine Frage.
Wenn die Datensätze [mm] S_1 [/mm] und [mm] S_2 [/mm] geordnet vorliegen, dann brauchst Du wesentlich weniger Vergleiche.
Ein Beispiel:
[mm] S_1=4,7,2,9,17,3
[/mm]
[mm] S_2=16,9,1,3,6,17,4,11
[/mm]
Diese Datensätze sind wohl nur in O(n) zu vereinigen. Je nach Algorithmus bekommst Du dann vielleicht
[mm] S_1 \cup S_2=4,7,2,9,17,3,16,1,6,11
[/mm]
Nehmen wir die gleichen Daten, aber geordnet:
[mm] S_1=2,3,4,7,9,17
[/mm]
[mm] S_2=1,3,4,6,9,11,16,17
[/mm]
Hier kann ich nun zwei Zeiger laufen lassen und die Mengen schnell vereinigen zu:
[mm] S_1 \cup S_2=1,2,3,4,6,7,9,11,16,17
[/mm]
Das ist eine Operation in O(1), wenn Du die Laufbedingung für die Zeiger richtig anlegst.
lg,
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:08 Di 30.12.2008 | | Autor: | Tasel |
Okay, ich hab mal ein bissel "gefummelt" und hoffe folgender Ansatz geht in die richtige Richtung:
$ [mm] K_{1} [/mm] $ und $ [mm] K_{2} [/mm] $ sollen nun doppelt verkettete Listen sein. Wenn ich nun die kürzere der beiden an die längere binde, indem ich den Zeiger der kürzeren auf das erste Element der längeren setze, dann erhalte ich eine Art Baum, in denen alle Elemente enthalten sind. Das schaffe ich mit einer Laufzeit von $ O(1) $, weil ich nur einen Zeiger ändern muss. Das Auslesen wäre dann zwar nicht $ O(1) $, dies ist aber auch nicht Teil der Aufgabenstellung.
Versuch es zu visualisieren:
--- --- --- --- --- ---
K1 | | -> | | -> | | -> | | -> | | -> | |
--- --- --- --- --- ---
--- --- ---
K2 | | -> | | -> | |
--- --- ---
VEREINIGUNG
--- --- --- --- --- ---
| | -> | | -> | | -> | | -> | | -> | |
--- --- --- --- --- / ---
K1 /
--- --- --- /
| | -> | | -> | | -
--- --- ---
|
|
|
| |
|
Na, wunderbar. Du hast es gelöst.
|
|
|
|
