Por que a complexidade de tempo do DFS e do BFS O (V + E)

O algoritmo básico para 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

Então, eu acho que a complexidade do tempo seria:

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

onde vé vértice 1den

Em primeiro lugar, o que eu disse correto? Em segundo lugar, como é isso O(N + E)e a intuição sobre o porquê seria realmente agradável. obrigado

Sua soma

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

pode ser reescrito como

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

e o primeiro grupo é O(N)enquanto o outro é O(E).

DFS (análise):

• Definir / obter um rótulo de vértice / borda leva O(1)tempo
• Cada vértice é rotulado duas vezes
  • uma vez que NÃO EXPLORADO
  • uma vez como VISITADO
• Cada aresta é rotulada duas vezes
  • uma vez que NÃO EXPLORADO
  • uma vez como DISCOVERY ou BACK
• O método incidentEdges é chamado uma vez para cada vértice
• O DFS é executado no O(n + m)tempo, desde que o gráfico seja representado pela estrutura da lista de adjacências
• Lembre-se que Σv deg(v) = 2m

BFS (análise):

• Definir / obter um rótulo de vértice / borda leva tempo O (1)
• Cada vértice é rotulado duas vezes
  • uma vez que NÃO EXPLORADO
  • uma vez como VISITADO
• Cada aresta é rotulada duas vezes
  • uma vez que NÃO EXPLORADO
  • uma vez como DESCOBERTA ou CRUZ
• Cada vértice é inserido uma vez em uma sequência Li
• O método incidentEdges é chamado uma vez para cada vértice
• O BFS é executado no O(n + m)tempo, desde que o gráfico seja representado pela estrutura da lista de adjacências
• Lembre-se que Σv deg(v) = 2m

Muito simplificado, sem muita formalidade: toda aresta é considerada exatamente duas vezes e todo nó é processado exatamente uma vez, portanto, a complexidade deve ser um múltiplo constante do número de arestas e do número de vértices.

A complexidade do tempo é O(E+V)substituída O(2E+V)porque, se a complexidade do tempo for n ^ 2 + 2n + 7, será escrita como O (n ^ 2).

Portanto, O (2E + V) é escrito como O (E + V)

porque a diferença entre n ^ 2 e n é importante, mas não entre n e 2n.

Eu acho que todas as arestas foram consideradas duas vezes e todos os nós foram visitados uma vez; portanto, a complexidade total do tempo deve ser O (2E + V).

Uma explicação intuitiva para isso é simplesmente analisando um único loop:

1. visite um vértice -> O (1)
2. um loop for em todas as arestas do incidente -> O (e) onde e é um número de arestas incidentes em um determinado vértice v.

Portanto, o tempo total para um loop único é O (1) + O (e). Agora some-o para cada vértice, pois cada vértice é visitado uma vez. Isto dá

For every V
=> 

    O(1)
    +

    O(e)

=> O(V) + O(E)

Explicação curta, mas simples:

No pior caso, você precisaria visitar todo o vértice e a margem, portanto, a complexidade do tempo no pior caso é O (V + E)