Изменения

Перейти к: навигация, поиск

Алгоритм Борувки

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

Навигация