322
правки
Изменения
Нет описания правки
==Асимптотика==
Сортировка <tex>E</tex> займет <tex>O(E\logElog E)</tex>.<br>
Работа с DSU займет <tex>O(E\alpha(V))</tex>, где <tex>\alpha</tex> - обратная функция Аккермана, которая не превосходит 5 во всех практических приложениях и которую можно принять за константу.<br>
Алгоритм работает за <tex>O(E(\logElog E+\alpha(E, V))) = O(E\logElog E) = O(E\logVlog V^2) = O(E\logVlog V)</tex>.
==См. также==
* [[Алгоритм Прима]]
