Изменения
→Асимптотика
==Асимптотика==
Сортировка <tex>E</tex> займет <tex>O(E\log E)</tex>.<br>
Для проверки возможности добавления ребра используется [[СНМ (реализация с помощью леса корневых деревьев) | система непересекающихся множеств]], работа с ней займет <tex>O(E\alpha(V))</tex>, где <tex>\alpha</tex> — обратная функция Аккермана, которая не превосходит <tex>4</tex> во всех практических приложениях и которую можно принять за константу.<br>
Алгоритм работает за <tex>O(E(\log E+\alpha(V))) = O(E\log E)</tex>.
