Kürzlich las ich dies und war überrascht, dass die zeitliche Komplexität der Union & amp; Finde Algorithmus nur mit der Pfadkomprimierung war O((m+n) log n) , wobei m die Anzahl der 'find' Abfragen und n die Anzahl der 'merge' Abfragen ist.
Ich war an dieser Komplexität interessiert (weil ich diesen Algorithmus normalerweise ohne Rang implementiere, und selbst wenn ich Vereinigung nach Rang verkehrt herum anwendete, war die Leistung nicht schlecht!) und versuchte, ein zu finden Beispiel, das diese Zeit Komplexität machen kann. Aber wegen der großen Kraft der Pfadkompression war es wirklich schwer ...
Gibt es Beispiele, die Omega((m+n) log n) erreichen können, oder ist diese Komplexität einfach theoretisch , nicht praktisch?
Ja, es gibt eine passende Untergrenze wegen Michael J. Fischers 1972 (siehe Abschnitt 3). Sein Beispiel verwendet einen Binomialbaum mit dem Tiefenlog n, wobei ein Binomialbaum mit der Tiefe 0 ein einzelner Knoten und ein Binomialbaum mit der Tiefe k zwei Binomialbäume mit der Tiefe k - 1 ist, wobei die Wurzel von eins auf die Wurzel des anderen zeigt . Indem wir wiederholt die Vereinigung der Wurzel des Binomialbaums auf einen Singleton zeigen und eine Suche auf dem tiefsten Knoten durchführen, führen wir eine teure (logarithmische Schritte) Operation durch, die einen anderen eingebetteten Binomialbaum ausnutzt.
Python-Demo: Dies gibt (k+1) * 2**k aus, wobei k das Argument für example ist und eine ungefähre Operationszahl für O(2**k) -Operationen auf O(2**k) keys darstellt.
oder ist diese Komplexität nur theoretisch, nicht praktisch?
Ja. Die Komplexität eines Algorithmus ist ein rein theoretisches Konstrukt, um how Nun der Algorithmus skaliert für verschiedene Eingabegrößen (in diesem Fall die Anzahl der Funde und Vereinigungen).
Dies gibt keine Garantie für die Anzahl der Schritte, die für eine bestimmte Instanz der Eingabe benötigt werden (sagen wir: 5 finds und 3 unions) - abgesehen davon, dass sie endlich ist. Tatsächlich verwendet die große O-Notation das Konzept einer beliebig großen multiplikativen Konstante, die aber nicht hilft, exakte Laufzeiten zu berechnen ist genug, um Algorithmen in Komplexitätsklassen zu unterscheiden.
Tags und Links algorithm disjoint-sets