¿Por qué la complejidad temporal de DFS y BFS O (V + E)

El 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

Entonces pensaría que la complejidad del tiempo sería:

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

donde ves el vértice 1den

En primer lugar, ¿es correcto lo que he dicho? En segundo lugar, cómo es esto O(N + E), y la intuición de por qué sería realmente agradable. Gracias

Su suma

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

puede reescribirse como

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

y el primer grupo es O(N)mientras que el otro es O(E).

DFS (análisis):

• Establecer / obtener una etiqueta de vértice / borde lleva O(1)tiempo
• Cada vértice está etiquetado dos veces
  • una vez como SIN EXPLORAR
  • una vez como VISITADO
• Cada borde se etiqueta dos veces
  • una vez como SIN EXPLORAR
  • una vez como DESCUBRIMIENTO o ATRÁS
• El método incidenteEdges se llama una vez para cada vértice
• DFS se ejecuta a O(n + m)tiempo siempre que el gráfico esté representado por la estructura de la lista de adyacencia
• Recordar que Σv deg(v) = 2m

BFS (análisis):

• Establecer / obtener una etiqueta de vértice / borde toma O (1) tiempo
• Cada vértice está etiquetado dos veces
  • una vez como SIN EXPLORAR
  • una vez como VISITADO
• Cada borde se etiqueta dos veces
  • una vez como SIN EXPLORAR
  • una vez como DESCUBRIMIENTO o CRUZ
• Cada vértice se inserta una vez en una secuencia Li
• El método incidenteEdges se llama una vez para cada vértice
• BFS se ejecuta a O(n + m)tiempo siempre que el gráfico esté representado por la estructura de la lista de adyacencia
• Recordar que Σv deg(v) = 2m

Muy simplificado sin mucha formalidad: cada borde se considera exactamente dos veces, y cada nodo se procesa exactamente una vez, por lo que la complejidad tiene que ser un múltiplo constante del número de bordes y el número de vértices.

La complejidad del tiempo es en O(E+V)lugar de O(2E+V)porque si la complejidad del tiempo es n ^ 2 + 2n + 7, entonces se escribe como O (n ^ 2).

Por lo tanto, O (2E + V) se escribe como O (E + V)

porque la diferencia entre n ^ 2 yn importa pero no entre n y 2n.

Creo que cada borde se ha considerado dos veces y cada nodo se ha visitado una vez, por lo que la complejidad del tiempo total debería ser O (2E + V).

Una explicación intuitiva para esto es simplemente analizando un solo bucle:

1. visitar un vértice -> O (1)
2. un bucle for en todos los bordes incidentes -> O (e) donde e es un número de bordes incidentes en un vértice dado v.

Entonces, el tiempo total para un solo ciclo es O (1) + O (e). Ahora suméelo para cada vértice ya que cada vértice se visita una vez. Esto da

For every V
=> 

    O(1)
    +

    O(e)

=> O(V) + O(E)

Breve pero simple explicación:

En el peor de los casos, necesitaría visitar todos los vértices y bordes, por lo tanto, la complejidad del tiempo en el peor de los casos es O (V + E)