Union-Find Beweis zur Laufzeit |
| 16.12.2017, 17:33 | Auf diesen Beitrag antworten » |
| dtrix | Union-Find Beweis zur Laufzeit Hallo, folgende Aufgabe ist gegeben: Wir betrachten die Union-Find-Datenstruktur, d. h. ein n-elementiges Feld A, in dem für jedes Element i in {1,...,n} gespeichert ist, zu welcher Menge es gehört. Zusätzlich ist für jede Menge ihre Größe und eine Liste der Elemente der Menge gegeben. In der Vorlesung wurde gezeigt, dass die Laufzeit für jede Folge von Union-Operationen auf n Elementen höchstens O(n logn) ist. Wie sieht eine Folge solcher Union-Operationen auf n Elementen aus, deren Laufzeit wirklich Theta(n logn) beträgt? Beweisen Sie Ihre Aussage. Beschränken Sie sich dabei auf den Fall, dass n eine Zweierpotenz ist. Das die Laufzeit für wiederholtes Aufrufen der Union Operation in Theta(logn) liegen kann verstehe ich noch, da ich die Teilmengen ja z.B. so vereinen kann: Ein x gehört erst zu einer Menge mit nur einem Element, dann mit 2 Elementen, 4, 8, .. bis 2^i=n Elementen, was logn Umhängeoperationen entspricht. Dann habe ich aber nurnoch eine Menge und für die anderen n-1 Elemente ist das nicht mehr anwendbar. Wie komme ich auf c*n*logn Operationen? Die Find(x) Operation liegt ja in O(n), fällt also raus. |
|
|
|
|
|
