Алгоритм Крускала следующий:
MST-KRUSKAL(G,w)
1. A={}
2. for each vertex v∈ G.V
3. MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v) ∈ G.E, taken in nondecreasing order by weight w
6. if FIND-SET(u)!=FIND-SET(v)
7. A=A U {(u,v)}
8. Union(u,v)
9. return A
По моему учебнику:
Инициализация множества A в строке 1 занимает O(1) времени, а время сортировки ребер в строке 4 равно O(E lgE). Цикл for в строках 5–8 выполняет операции O(E) FIND-SET и UNION в лесу непересекающихся множеств. Наряду с |V| Операции MAKE-SET занимают в общей сложности O((V+E)α(V)) времени, где α — очень медленно растущая функция. Поскольку мы предполагаем, что G связна, мы имеем |E| ‹= |V|-1, поэтому операции над непересекающимися множествами занимают время O(E α(V)). Более того, поскольку α(V)=O(lgV)=O(lgE), общее время работы алгоритма Крускала составляет O(E lgE). Заметив, что |E|‹|V|^2, мы имеем lg |E|=O(lgV), поэтому мы можем переформулировать время работы алгоритма Крускала как O(E lgV).
Не могли бы вы объяснить мне, почему мы делаем вывод, что время сортировки ребер в строке 4 равно O(E lgE)? Также как мы получаем, что общая временная сложность равна O((V+E)α(V)) ?
Кроме того, предположим, что все веса ребер в графе являются целыми числами от 1 до |V|. Как быстро вы можете заставить работать алгоритм Крускала? Что, если веса ребер являются целыми числами в диапазоне от 1 до W для некоторой константы W?
Как временная сложность зависит от веса ребер?
ИЗМЕНИТЬ:
Кроме того, предположим, что все веса ребер в графе являются целыми числами от 1 до |V|. Как быстро вы можете заставить работать алгоритм Крускала?
Я подумал следующее:
Чтобы алгоритм Крускала работал быстрее, мы можем отсортировать ребра, применяя сортировку подсчетом.
- Строка 1 требует O(1) времени.
- Строки 2-3 требуют времени O(v).
- Строка 4 требует O(|V|+|E|) времени.
- Строки 5-8 требуют O(|E|α(|V|)) времени.
- Строка 9 требует O(1) времени.
Итак, если мы используем сортировку подсчетом для решения ребер, временная сложность Крускала будет
Скажите, верна ли моя идея?
Также:
Что, если веса ребер являются целыми числами в диапазоне от 1 до W для некоторой константы W?
Мы снова будем использовать сортировку подсчетом. Алгоритм будет тот же. Находим временную сложность следующим образом:
- Строка 1 требует O(1) времени.
- Строки 2-3 требуют времени O(|V|).
- Строка 4 требует O(W+|E|)=O(W)+O(|E|)=O(1)+O(|E|)=O(|E|) времени.
- Строки 5-8 требуют O(|E|α(|V|)) времени.
- Строка 9 требует O(1) времени.
Таким образом, временная сложность будет:
