Что лучше O (V + E) или O (ElogE)?
Я пытаюсь разработать алгоритм, который сможет найти минимальное остовное дерево из графа. Я знаю, что для него уже существует много существующих алгоритмов. Однако я пытаюсь исключить сортировку ребер, требуемую в алгоритме Крускала. Алгоритм у меня есть. Разработанная до сих пор часть, в которой необходим подсчет непересекающихся множеств, и мне нужен эффективный метод для этого. После долгих исследований я узнал, что единственный возможный способ - использовать BFS или DFS со сложностью O (V + E) тогда как алгоритмы Крускала имеют сложность O (ElogE). Теперь мой вопрос: какой из них лучше, O (V + E) или O (ElogE)?
@Srini Вы не можете предполагать, что цикла нет, поскольку вопрос заключается в вычислении минимального остовного дерева графа (так неориентированного и с потенциально нетривиальными циклами). Однако, предполагая, что существует дерево, которое нужно найти, мы можем с уверенностью предположить, что V <= E
@Rerito хороший момент, я проигнорировал аспект циклов, потому что я не был уверен, что делать с компонентом F в V - E + F = 2 для формулы Эйлера для плоских графов. Но я полагаю, что если ОП или кто-то другой сможет выяснить, как с этим справиться, или докажет, что V все еще имеет линейную связь с E, тогда, я думаю, они все равно могли бы опираться на этот аргумент
Параллельное выполнение обоих алгоритмов и остановка, как только один из них завершится, дает вам сложность O(min(V+E, E Log E)), которая всегда является лучшей.
Ответы 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).
Другой способ взглянуть на это - увидеть, что в нотации с большим О O(X + Y) означает то же, что и O(max(X, Y)).
Обратите внимание, что это полезно только тогда, когда V и E могут иметь одинаковую величину. Для алгоритма Краскала доминирующим фактором является то, что вам нужно отсортировать список ребер. Независимо от того, есть ли у вас разреженный граф или плотный граф, этот шаг преобладает над всем, что может быть O(V), поэтому просто пишут O(E lg E) вместо O(V + E lg E).
Не могли бы вы дать представление об O (ElogE)?
Алгоритм Краскала включает в себя сортировку списка ребер, поэтому независимо от того, есть ли у вас разреженный или плотный граф, он будет преобладать над затратами на простую итерацию по неупорядоченному списку. Термин «аддитивный» V не имеет значения в любом случае, поэтому пишут просто O(E lg E), а не O(V + E lg E).
Предполагая, что циклов нет,
Vможно выразить черезE, используя формулу Эйлера. Следовательно,O(V+E)на самом деле простоO(E). Начиная сO(n) < O(nlogn),O(E + V) ~= O(E) < O(ElogE). Я не уверен в своих расчетах, поэтому размещаю это как комментарий, а не как ответ