Я пытаюсь реализовать BFS и DFS в Java в качестве общего алгоритма. Я пишу метод getComplexity(), который возвращает наихудшую сложность алгоритма в виде строки. В DFS (и BFS) каждый узел в графе можно посещать только один раз. В худшем случае каждый узел посещается только один раз. Следовательно, почему сложность этих алгоритмов O (V + E) вместо O (V)? Здесь V - количество узлов (или вершин), а E - количество ребер.Почему сложность DFS и BFS не O (V)?
Обход дерева (BFS и DFS) - это O (V + E), потому что каждое ребро должно проходить ровно один раз, и каждый узел должен посещаться ровно один раз. Обход дерева часто является абстракцией, которая помогает нам взглянуть на проблему. В большинстве простых случаев, как V, так и E являются тривиальными операциями, однако это не всегда так, и эффективность V может радикально отличаться от E. Например, пересечение ребра может быть таким же простым, как и указатель, или он может требуют, чтобы вы извлекали данные с удаленного хоста по сети (возможно, с использованием дорогостоящего запроса к базе данных). Посещение узла может быть таким же простым, как установка логического значения, или это может потребовать выполнения некоторых дорогостоящих вычислений по данным на этом узле.
O (V + E) напоминает нам, что мы должны учитывать как сложность узлов посещения, так и пересекающихся ребер, когда мы рассуждаем об общей сложности пересечения дерева.
Ухаживать за голосом? – Aurand
Я не думаю, что дифференциация между указателями и внешними запросами базы данных имеет какое-либо отношение к абстрактному большому алгоритму, а тем более к настройке логического значения по сравнению с выполнением дорогостоящих вычислений. Это постоянные факторы – torquestomp
@torquestomp Я думал, что конкретный пример поможет продемонстрировать, почему V! = E. Если V = E. O (V + E) = O (2V) и в больших-Oh O (2V) упрощается до O (V), так как в любом дереве число ребер равно числу узлов - 1. – Aurand
Потому что в общем графике E (то есть количество ребер) может быть как V*(V-1)/2 (для полного графика), который составляет V^2. Поэтому мы не можем просто игнорировать тот факт, что нам нужно проверять каждое ребро (с целью поиска невидимых узлов), поскольку эта проверка может стоить больше (как я сказал, это может быть V^2), чем стоимость посещения каждого узла (который всегда V).
Каждый узел посещается один раз, каждый край проходит один раз. Следовательно, O (V + E). – Aurand
Это, кажется, не дубликат для меня. ОП в вопросе, который вы опубликовали, понимает, почему он (v1 + e1 + v2 + e2 ...). Но здесь ОП спрашивает, почему это так. – Cricketer