Почему временная сложность как 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), и интуиция относительно того, почему было бы действительно приятно. Благодаря

Ответы

Ответ 1

Ваша сумма

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).

Ответ 2

ДФС (анализ):

  • Установка/получение метки вершины/края занимает O(1) время
  • Каждая вершина помечена дважды
    • один раз как UNEXPLORED
    • один раз как ПОСЕТИЛ
  • Каждый ребро помечен дважды
    • один раз как UNEXPLORED
    • один раз как DISCOVERY или BACK
  • Метод randomEdges вызывается один раз для каждой вершины
  • DFS работает в O(n + m) времени, если граф представлен структурой списка смежности
  • Напомним, что Σv deg(v) = 2m

BFS (анализ):

  • Установка/получение метки вершины/края принимает O (1) время
  • Каждая вершина помечена дважды
    • один раз как UNEXPLORED
    • один раз как ПОСЕТИЛ
  • Каждый ребро помечен дважды
    • один раз как UNEXPLORED
    • один раз как DISCOVERY или CROSS
  • Каждая вершина вставляется один раз в последовательность Li
  • Метод randomEdges вызывается один раз для каждой вершины
  • BFS работает в O(n + m) времени, если граф представлен структурой списка смежности
  • Напомним, что Σv deg(v) = 2m

Ответ 3

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

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

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

Ответ 7

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

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

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

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>