In dieser Implementierung des Quick Find-Algorithmus benötigt Constructor N steps, also union() .
Der Kursleiter hat gesagt, dass union zu teuer ist, weil N^2 zur Prozesssequenz von N union Befehle von N benötigt, Wie kann union quadratisch sein, wenn es auf Array zugreift Elemente einzeln nacheinander?
Jeder Aufruf der Methode union erfordert, dass Sie über das Array id iterieren, was O(n) time benötigt. Wenn Sie union method n mal aufrufen, ist die benötigte Zeit n*O(n) = O(n^2) .
Sie können die Zeitkomplexität von union method auf O(1) verbessern, indem Sie die Zeitkomplexität der verbundenen Methode höher machen, wahrscheinlich O(log n) , aber dies ist nur eine einmalige Operation. Ich glaube, dass dein Lehrbuch das im Detail erklärt.
Beachten Sie, dass der Algorithmus Schnellsuche aufgerufen wird, da jede Operation zum Suchen ( Es gibt einen weiteren Algorithmus Quick Union , der die Zeit für Union Operation für Schnellsuche ist quadratisch O(n^2) für n operations, weil jede Operation O(n) time benötigt, was in for loop in union(int p, int q) connected(int p, int q) ) konstante Zeit benötigt. Für diesen Algorithmus zahlen Sie jedoch in union operation, wie in Ihrer Frage erwähnt. union operation verbessert. Aber dann bleibt find nicht O(1) (aber besser als lineare Zeit).