Почему временная сложность как DFS, так и BFS O(V + E)

основной алгоритм для BFS:

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

поэтому я думаю, что сложность времени будет:

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

здесь v - это вершина 1 до n

во-первых, то, что я сказал правильно? Во-вторых, как это O(N + E), и интуиция относительно того, почему было бы действительно приятно. Спасибо

7 99
algorithm core-graphics time-complexity breadth-first-search

7 ответов:

ваша сумма

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

можно переписать в виде

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

и первая группа составляет O(N) в то время как другой O(E).

215

DFS (анализ):

  • установка / получение метки вершины / края занимает O(1) времени
  • каждая вершина помечена дважды
    • однажды как неизведанное
    • один раз как посетил
  • каждый край помечается дважды
    • однажды как неизведанное
    • один раз как открытие или обратно
  • метод incidentEdges вызывается один раз для каждой вершины
  • DFS работает в O(n + m) время при условии, что график представлен структурой списка смежности
  • Напомним, что Σv deg(v) = 2m

BFS (анализ):

  • установка/получение метки вершины / края занимает O (1) времени
  • каждая вершина помечена дважды
    • однажды как неизведанное
    • один раз как посетил
  • каждый край помечается дважды
    • однажды как неизведанное
    • один раз как открытие или Крест
  • каждая вершина вставляется один раз в последовательность Li
  • метод incidentEdges вызывается один раз для каждой вершины
  • BFS работает в O(n + m) время при условии, что график представлен структурой списка смежности
  • Напомним, что Σv deg(v) = 2m
35

очень упрощено без особых формальностей: каждое ребро рассматривается ровно дважды, и каждый узел обрабатывается ровно один раз, поэтому сложность должна быть постоянной кратной числу ребер, а также числу вершин.

18

сложность времени O(E+V) вместо O(2E+V) потому что если временная сложность равна n^2+2n+7, то она записывается как O(n^2).

следовательно, O(2E+V) записывается как O (E+V)

потому что разница между n^2 и n имеет значение, но не между n и 2n.

8

Я думаю, что каждое ребро было рассмотрено дважды, и каждый узел был посещен один раз, поэтому общая сложность времени должна быть O(2E+V).

3

короткое, но простое объяснение:

в худшем случае вам нужно будет посетить все вершины и края, следовательно временная сложность в худшем случае равна O (V+E)

1

интуитивное объяснение этому заключается в простом анализе одного цикла:

  1. посетите вершину - > O (1)
  2. a для цикла на всех падающих ребрах - > O (e) где e-число ребер, падающих на заданную вершину v.

таким образом, общее время одного цикла составляет O(1)+О(Е). Теперь суммируйте его для каждой вершины, так как каждая вершина посещается один раз. Это дает

Sigma_i

p {
    height: 50px;
    line-height: 50px;
}

span {
    position: relative;
    font-size: 2.5em;
    display: inline-block;
    line-height: .7em;
    vertical-align: middle;
}

span:before {
    font-size: 12px;
    display: block;
    position absolute;
    left: 0;
    top: 0;
    content: "V";
    width: 22px;
    text-align: center;
}

span:after {
    font-size: 12px;
    display: block;
    position absolute;
    left: 0;
    bottom: 0;
    content: "k = 1";
    width: 27px;
    text-align: center;
}
<p>
    <span>&Sigma;</span>
    O(1) + O(e)
=> 
    <span>&Sigma;</span>
    O(1)
    +
   <span>&Sigma;</span>
    O(e)

=> O(V) + O(E)

</p>

[ O (1) + O (e)]

0