Продолжительность алгоритма Крускала, изменяя время сортировки

Question

Я занимался анализом минимальных связующих деревьев и задавался вопросом, как время сортировки повлияет на общую временную сложность алгоритма Крускаля?

Пример:

1. Если сортировка может быть сделано в O(n log log n)
2. Если сортировка может быть сделано в O(n)

ли ответ по-прежнему остаются O(e log n) для обоих случаев или это изменить?

Answer 1

Время алгоритма Крускаля - O(e log e) и его время для сортировки ребер. Если вы можете сделать это в O (e), учитывая, что остальная часть алгоритма для поиска минимального остовного дерева равна O (e log n), у вас есть O(e) + O(e log n). Начиная с e=O(n^2), тогда время алгоритма будет O(n^2 log n) или O(e log n). если сортировка принимает O (e log log e) с тем же анализом, общее время будет O(e log log e).

Подробности: Время для нахождения минимального остовного дерева вычисляется по времени вам нужно для сортировки ребер, а затем петли (е раз), в котором вы удалить каждое ребро из отсортированного списка и исследовать, если он соединяет два непересекающихся регионов или нет. (эта проверка требует O (log n)), и время цикла будет O(e log n), как указано выше.

с использованием более сложной непересекающимся набором структуры данных, чтобы найти и проверить непересекающиеся области петли имеет О (Е α (V)) время, где α является крайне медленно растет обратный однозначную функцию Ackermann (WikiPedia)

Answer 2

Если вы используете непересекающийся набор для реализации Крускала сложность алгоритма будет SortComplexity+Eα(E)

(E этим число ребер и alpha очень медленно растут функцию (по wikipedia менее 5 для Практической ценности n))

Так что если сортировка может быть сделано в O(n) то сложность Крускала будет O(E α(E))

И если сортировка сложности O(nloglogn) сложность Крускала будет O(EloglogE) и плотного графика будет O(v^2loglogv) (v это число вершин)