prev up inhalt next


4.0.1 Satz von Tarjan

Der Aufwand um m-mal Union/Find durchzuführen beträgt m · $\alpha$(m,n) , wobei $\alpha$ die inverse Ackermannfunktion darstellt, eine stark steigende Funktion.

Das bedeutet, daß Union/Find in fast konstanter Zeit abläuft.


prev up inhalt next