Почему сложность по времени как 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)

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

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

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

 12 сент. 2015 г., 13:31
Я убрал свое понижениеonly потому что вы отредактировали свой ответ,
 10 сент. 2015 г., 19:38
@Am_I_Helpful, что кто-то спрашивает выше 2E в нотации big-oh ... вот почему 2 не учитывается во временной сложности.
 12 сент. 2015 г., 11:59
@Am_I_Helpful, просто посмотрите пост выше моего ответа ... там пользователь по имени Kehe CAI написал "Я думаю, что каждое ребро было рассмотрено дважды, и каждый узел был посещен один раз, поэтому общая сложность времени должна быть O (2E +"). V), & Quot. Так что я ответил соответственно .... Понял !!!

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

I the worst case you would need to visit all the vertex and edge hence the time complexity in the worst case is O(V+E)

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

 21 апр. 2016 г., 03:52
Большой О анализ игнорирует константу. O (2E + V) является O (E + V).
 04 авг. 2015 г., 08:47
Даже я чувствую то же самое. Кто-нибудь может дать дальнейшие объяснения по этому поводу?
Решение Вопроса

Ваша сумма

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

 26 янв. 2016 г., 04:19
log (| Q |) & lt; log (N) & lt; N, следовательно, вы можете смело игнорировать термин в асимптотике
 24 янв. 2016 г., 11:56
Но каждая вершина должна быть извлечена из очереди, и это log (| Q |) Как насчет этой части?
 24 февр. 2017 г., 09:29
Если в списке смежности каждая вершина связана со всеми остальными вершинами, сложность будет эквивалентна O (V + E) = O (V + V ^ 2) = O (V ^ 2). E = V ^ 2, потому что наибольшее количество ребер = V ^ 2.
 30 апр. 2017 г., 11:17
Согласно вашему ответу, сложность не станет O (V + 2E)? Поскольку каждое ребро может иметь общее ребро с другим ребром?
 04 мая 2017 г., 15:58
Постоянные условия могут быть отброшены.

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

visit a vertex -> O(1) a for loop on all the incident edges -> O(e) where e is a number of edges incident on a given vertex 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>

[O (1) + O (e)]

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

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

Setting/getting a vertex/edge label takes O(1) time Each vertex is labeled twice once as UNEXPLORED once as VISITED Each edge is labeled twice once as UNEXPLORED once as DISCOVERY or BACK Method incidentEdges is called once for each vertex DFS runs in O(n + m) time provided the graph is represented by the adjacency list structure Recall that Σv deg(v) = 2m

BFS (анализ):

Setting/getting a vertex/edge label takes O(1) time Each vertex is labeled twice once as UNEXPLORED once as VISITED Each edge is labeled twice once as UNEXPLORED once as DISCOVERY or CROSS Each vertex is inserted once into a sequence Li Method incidentEdges is called once for each vertex BFS runs in O(n + m) time provided the graph is represented by the adjacency list structure Recall that Σv deg(v) = 2m
 02 дек. 2014 г., 13:18
спасибо за конкретность, упомянув, что графы должны быть представлены структурой списка смежности, меня беспокоило, почему DFS - O (n + m), я бы подумал, что это O (n + 2m), потому что каждое ребро пересекается дважды возвращаясь назад.
 13 июл. 2012 г., 12:36
tnx для редактирования, я здесь новенький, так что я все еще пытаюсь справиться с экраном редактирования :)

Ваш ответ на вопрос