Время выполнения алгоритма Крускала путем изменения времени сортировки

Question

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

Пример:

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

Остался бы ответ? O(e log n) для обоих случаев или это изменится?

Answer 1

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

(E это число ребер и alpha очень медленно растущая функция (согласно Википедии менее 5 для практического значения n))

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

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

Answer 2

Время алгоритма Крускала составляет 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),

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

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