Анализ сложности по сложности

Сложность времени для перемещения по смежным ребрам вершины называется O(N), где N - число соседних ребер. Таким образом, для V числа вершин сложность времени становится O(V*N)= O(E), где E - общее количество ребер в графе. Поскольку удаление и добавление вершины из/в очередь равно O(1), почему она добавляется к общей временной сложности BFS как O(V+E).

Ответы

Ответ 1

Надеюсь, это поможет любому, кто не понимает сложность вычислительного времени для Breadth First Search a.k.a BFS.

Queue graphTraversal.add(firstVertex);

// This while loop will run V times, where V is total number of vertices in graph.
while(graphTraversal.isEmpty == false)

    currentVertex = graphTraversal.getVertex();

    // This while loop will run Eaj times, where Eaj is number of adjacent edges to current vertex.
    while(currentVertex.hasAdjacentVertices)
        graphTraversal.add(adjacentVertex);

    graphTraversal.remove(currentVertex);

Сложность времени такова:

V * (O(1) + Eaj + O(1))
V + V * Eaj + V
2V + E(total number of edges in graph)
V + E

Я попытался упростить вычисление кода и сложности, но все же, если у вас есть какие-либо вопросы, дайте мне знать.

Ответ 2

Учитывая следующий график, мы видим, как сложность времени O (| V | + | E |), но не O (V * E).

Список привязанностей

V     E
v0:{v1,v2} 
v1:{v3}
v2:{v3}
v3:{}

Операция Как работает BFS Шаг за шагом

Шаг 1:

Списки смежности:

V     E
v0: {v1,v2} mark, enqueue v0
v1: {v3}
v2: {v3}
v3: {}

Шаг 2:

Списки смежности:

V     E
v0: {v1,v2} dequeue v0;mark, enqueue v1,v2
v1: {v3}
v2: {v3}
v3: {}

Шаг 3:

Списки смежности:

V     E
v0: {v1,v2}
v1: {v3} dequeue v1; mark,enqueue v3
v2: {v3}
v3: {}

Шаг 4:

Списки смежности:

V     E
v0: {v1,v2}
v1: {v3}
v2: {v3} dequeue v2, check its adjacency list (v3 already marked)
v3: {}

Шаг 5:

Списки смежности:

V     E
v0: {v1,v2}
v1: {v3}
v2: {v3}
v3: {} dequeue v3; check its adjacency list

Шаг 6:

Списки смежности:

V     E
v0: {v1,v2} |E0|=2
v1: {v3}    |E1|=1
v2: {v3}    |E2|=1
v3: {}      |E3|=0

Общее количество шагов:

|V| + |E0| + |E1| + |E2| +|E3| == |V|+|E|
 4  +  2   +  1   +   1  + 0   ==  4 + 4
                           8   ==  8

Предположим представление списка смежности, V - число вершин, E - количество ребер.

Каждая вершина помещается в очередь и выгружается не более одного раза.

Сканирование всех смежных вершин занимает время O (| E |), так как сумма длин списков смежности | E |.

Следовательно, сложность времени BFS дает сложность времени O (| V | + | E |).

Ответ 3

Выполняя O(1) операцию L раз, результат в O(L) сложности. Таким образом, удаление и добавление вершины из/в очередь - O (1), но когда вы делаете это для вершин V, вы получаете сложность O(V). Поэтому O(V) + O(E) = O(V+E)

Ответ 4

I understood the part V+E in the complexity.
But I have 2 questions
1). V * Eaj should give 2E?
(as it is the total no of edges accessed, and each edge is checked twice, by each of it ends)

2) Also the complexity is V + E
but in worst case we take E = V*(V-1)/2
So V isn't required here as we could say we  E = V²...
Can't we say complexity O(E) only?