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

DFS(análisis):

• Establecer / obtener una etiqueta de vértice/borde toma O(1) tiempo
• Cada vértice se etiqueta dos veces
  • una vez como INEXPLORADO
  • una vez visitado
• Cada borde se etiqueta dos veces
  • una vez como INEXPLORADO
  • una vez como DESCUBRIMIENTO o VUELTA
• El método incidentEdges se llama una vez para cada vértice
• DFS se ejecuta en O(n + m) tiempo siempre que el gráfico esté representado por la lista de adyacencia estructura
• Recuerda que Σv deg(v) = 2m

BFS (análisis):

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

Muy simplificado sin mucha formalidad: cada arista 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 aristas, así como el número de vértices.

La complejidad temporal es O(E+V) en lugar de O(2E+V) porque si la complejidad temporal 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 y n 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 total de tiempo debe ser O(2E+V).

Breve pero sencilla explicación:

I el peor de los casos que tendría que visitar todos los vértices y aristas por lo tanto la complejidad temporal en el peor de los casos es O (V+E)

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

1. visita 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.

Así que el tiempo total para un solo bucle es O(1)+O(e). Ahora sum para cada vértice como cada vértice se visita una vez. Esto da

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