Какой из них лучше O (V + E) или O (ElogE)?

Question

Я пытаюсь разработать алгоритм, который сможет найти минимальное остовное дерево из графа. Я знаю, что для него уже существует много алгоритмов. Однако я пытаюсь устранить сортировку ребер, требуемую в алгоритме Крускала. Алгоритм, который я разработал до сих пор, имеет часть, в которой необходим подсчет непересекающихся множеств, и мне нужен эффективный метод для него. После долгих исследований я узнал, что единственный возможный способ - это использование BFS или DFS со сложностью O (V + E), тогда как алгоритмы Крускала имеют сложность O (ElogE). Теперь мой вопрос, какой из них лучше, O (V + E) или O (ElogE)?

Answer 1

Как правило, E = O(V^2), но эта граница может быть не жесткой для всех графиков. В частности, в разреженном графе E = O(V), но для сложности алгоритма обычно указывается значение наихудшего случая.

O(V + E) - это способ указать, что сложность зависит от количества ребер. В разреженном графе O(V + E) = O(V + V) = O(V), а в плотном графе O(V + E) = O(V + V^2) = O(V^2).

Другой способ взглянуть на это состоит в том, чтобы увидеть, что в нотации big-O O(X + Y) означает то же самое, что и O(max(X, Y)).

Обратите внимание, что это полезно только тогда, когда V и E могут иметь одинаковую величину. Для алгоритма Крускала доминирующим фактором является необходимость сортировки списка ребер. Независимо от того, есть ли у вас разреженный граф или плотный граф, этот шаг доминирует над всем, что может быть O(V), поэтому просто пишите O(E lg E) вместо O(V + E lg E).