Union-Find < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:00 Di 07.12.2010 | | Autor: | salwa |
| Aufgabe | Zeigen Sie, dass, falls beginnend bei der Partition {{1},...,{n}} erst UNIONs und dann FINDs durchgefu ̈hrt werden, diese Operationen amortisiert konstante Laufzeit haben.
Hinweis: Ordnen Sie die Kosten jeder bei einem FIND durchlaufenen Kante, bis auf die letzte, einer UNION-Operation zu. |
hallo, ich hoffe meine Frage ist richtig hier!
Also wenn man zwei Bäume zusammenfügt, erstellt man eine Kante zwischen den Wurzeln von jedem Baum und damit den kleineren zu Unterteilbaum von größerem macht. Diese UNION-Operation kostet O(1).
FIND-Operation im Gegensatz kostet O(logn), oder wenn man "Pfadkompression" einsetzt (bei Finde-Operation werden alle Knoten auf dem Pfad bis zur Wurzel "aufgesammelt" und direkt an die Wurzel angehangen), diese verkürzt dann spätere Finde-Operation auf O(f(n)), wobei f ist eine Funktion.
Wenn ich die Partition bis k mit [mm] 1\le [/mm] k [mm] \le [/mm] n nehme und UNION anwende, wie soll ich die einer Finde-Operation einordnen die Laufzeiten sind doch unterschiedlich? Oder, jede neue eingefügte Kante direkt an der Wurzel anhängen, und damit habe ich mit einem Zugriff den gesuchten Knoten..
ich siehe selber das ist nicht wirklich Klever.
Kann jemand mir bitte ein paar Tipps, wie ich an die Aufgabe rangehen soll? ich meine der Hinweis von der Aufgabe ist nicht unbedingt hilfsreich..
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Vielen Dank
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Fr 10.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
