394
правки
Изменения
→Асимптотика
Время работы внутри главного цикла будет равно <tex>O(E + V)</tex>.
Количество итераций, которое выполняется главным циклом равно <tex>O(\log{V})</tex> так как на каждой итерации количество компонент связанности связности уменьшается в 2 раза (изначально количество компонент равно <tex>|V|</tex>, в итоге должна стать одна компонента).
Общее время работы алгоритма получается <tex>O(E\log{V})</tex>.
