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

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


algorithm time-complexity graph-theory breadth-first-search kruskals-algorithm
person Afsana Khan    schedule 01.05.2018    source источник
comment
Предполагая, что циклов нет, V можно выразить через E по формуле Эйлера. Поэтому O(V+E) на самом деле просто O(E). С O(n) < O(nlogn), O(E + V) ~= O(E) < O(ElogE) . Я не уверен в своей математике, поэтому публикую это как комментарий, а не ответ   -  person Srini    schedule 01.05.2018
comment
@Srini Вы не можете предполагать, что цикла нет, поскольку вопрос заключается в вычислении минимального остовного дерева графа (настолько неориентированного и с потенциально нетривиальными циклами). Однако, предполагая, что есть дерево, которое нужно найти, мы можем с уверенностью предположить, что V <= E   -  person Rerito    schedule 01.05.2018
comment
@Rerito хорошая мысль, я проигнорировал аспект циклов, потому что не знал, как поступить с компонентом F V - E + F = 2 для формулы Эйлера для плоских графов. Но я полагаю, что если бы ОП или кто-то еще мог выяснить, как с этим справиться, или доказать, что V по-прежнему имеет линейную связь с E, то я думаю, что они все еще могли бы опираться на этот аргумент.   -  person Srini    schedule 01.05.2018
comment
Запуск обоих алгоритмов параллельно и остановка, как только один из них завершится, дает вам сложность O(min(V+E, E Log E)), которая всегда является лучшей.   -  person Yves Daoust    schedule 01.05.2018

Ответы (1)


arrow_upward
0
arrow_downward

Как правило, 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).

person chepner    schedule 01.05.2018
comment
Не могли бы вы дать представление об O (ElogE)? - person Afsana Khan; 01.05.2018
comment
Алгоритм Крускала включает в себя сортировку списка ребер, поэтому независимо от того, есть ли у вас разреженный или плотный граф, стоимость простого перебора неупорядоченного списка будет выше. Дополнительный термин V в любом случае не имеет значения, поэтому просто пишут O(E lg E), а не O(V + E lg E). - person chepner; 01.05.2018