Diskussion:Union-Find-Struktur

$\log ^{*}$ hab ich bei Algorithmus von Kruskal erklärt, eigentlich gehört es aber in ein eigenes Lemma - nur wo? Samx 15:12, 18. Jul. 2007 (CEST)

Die allerletzte Zeile kann so nicht Stimmen, da wenn weder u noch f von n abhängen die Laufzeit > O(n) wäre und sich der ganze Aufwand mit Pfadkompression nicht lohnen würde.

Habe es korrigiert. --78.53.209.157 11:50, 3. Jul. 2009 (CEST)

Kann mir einer erklären warum union mit Bäumen ohne Verbesserung O(1) Zeit benötigen soll ? Ich behaupte mal, das ist falsch, weil union mittels find den Weg bis zur Wurzel abgeht (also O(n) bei entartetem Baum). Danke ! --Webskipper 13:06, 21. Mai 2010 (CEST)

Jetzt sehe ich, dass Union hier ganz anders definiert ist, wie z.B. im Cormen oder auch der englischen Wikifassung. In der deutschen Fassung werden Repräsentanten (Wurzelknoten) als Parameter übergeben. Meinem Verständnis nach ist das falsch. Würde das gerne klären, vor allem ist hier kein Hinweis auf Quellen / Literatur. --Webskipper 13:15, 21. Mai 2010 (CEST)

Lemma und Kauderwelsch

Fremdworte sind, wenn sinnvoll, natürlich zu benutzen, logisch. Die Grenze des Sinnvollen ist zwar strittig aber hier auch nicht mein Thema. Völlig inakzeptabel und nicht zu beschönigen sind aber denglisches Kauderwelsch und lustige Phantasieanglizismen als scheinbar internationale Fachbegriffattrappen (Beispiele: Union-Find-Struktur, Make-Set, Union-By-Size oder Pointer-Maschinen Modell und Cell-Probe Modell). Reichlich Deppenbindestriche machen die Wortschöpfungen erst so richtig rund. Als Programmierer sind mir die Marotten meiner geltungssüchtigen Kollegen ja bekannt und lästig; die können Niemandem auf Deutsch erklären, was sie oder ihre Programme machen, und ein englischer Muttersprachler versteht sie auch nicht; im Gegensatz zu den durchschnittlichen deutschen Provinzweltbürgern ist aber wenigstens deren englische Grammatik korrekt. Besonders peinlich werden solche Schaumschlägereien, wenn im englischen Parallelartikel diese "Fachbegriffe" nicht vorkommen oder das Gemeinte mit einem andere englischen (Fach-) Begriff bezeichnet wird. Beispiele gefällig: "Union-Find-Struktur" heißt auf Englisch wohl "Disjoint-set data structure", oder "Union-By-Size" ist "union by rank".

Es ist auch komisch, daß von den zZ 16 verschiedensprachlichen Artikeln zum Thema nur 3 einen irgendwie englischen Titel haben: englisch, deutsch und überraschenderweise französisch. Aber daß der englische Titel nicht mit dem denglischen übereistimmt ist besonders merkwürdig. Dann kann "Union-Find-Struktur" also nur mal wieder ein typisch deutscher Scheinanglizismus sein. Wie peinlich...--46.115.138.138 22:49, 12. Jun. 2014 (CEST)

Ich würde das Lemma Union-Find Datenstruktur benennen. Union-Find hat sich als Fachbegriff im Deutschen und Englischen (!!) einfach eingebürgert? Im Englischen gibt es übrigens eine Weiterleitung von Union Find. Hier sollte man wohl nicht nur inter-Wiki Links als Quellen benutzen. Zugegeben, manchmal sollte man sich vor dem vorschnellen benutzen von Anglizismen, überlegen ob es ein gebräuchliches(!) Gegenstück in der Deutschen Sprache gibt. Dieses Lemma bietet hier wohl einige Beispiele. Fantastisierende Wortschöpfungen sind aber keinesfalls besser. Wie soll man denn bitte schön z.B. cell-probe ins Deutsche übersetze, sodass danach noch klar ist, was man damit meint? Im Übrigen finde ich ein allgemeines Bashing von Programmiererkollegen auf der Disk. an dieser Stelle fehl am Platz. --Andreschulz (Diskussion) 16:16, 1. Jul. 2014 (CEST)

Worst-case Laufzeit Union

Wieso ist bei "Union-By-Size mit Pfadkompression" die Worst-Case Laufzeit O(1)? Meinem Verständnis nach würde man die Größen der Bäume an der Wurzel speichern, und bei einer Union Operation zweier Elemente zuerst eine find-Operation für beide Elemente ausführen, um anschließend entsprechend auf die Größen zugreifen zu können. Demnach müsste die Worst-Case Laufzeit, denke ich, O(log n) sein. Oder übersehe ich eine andere Art und Weise, das zu machen? --95.90.205.102 10:21, 27. Mär. 2024 (CET)