algorithm - first - ¿Por qué es la complejidad de tiempo de DFS y BFS O(V+E)

deep first search algorithm

Question

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, creo que la complejidad del tiempo sería:

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

donde v es el vértice 1 a n

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

Answer 1

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)

Answer 2

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

Answer 3

DFS (análisis):

• Establecer / obtener una etiqueta de vértice / borde toma O(1) vez
• Cada vértice está etiquetado dos veces
  • una vez como INEXPLORADO
  • una vez como VISITADO
• Cada borde está etiquetado dos veces
  • una vez como INEXPLORADO
  • una vez como DESCUBRIMIENTO o ATRÁS
• Método incidenteEdges 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 estructura de la lista de adyacencia
• Recuerde que Σv deg(v) = 2m

BFS (análisis):

• Establecer / obtener una etiqueta de vértice / borde toma O (1) vez
• Cada vértice está etiquetado dos veces
  • una vez como INEXPLORADO
  • una vez como VISITADO
• Cada borde está etiquetado 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 incidenteEdges 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 la lista de adyacencia
• Recuerde que Σv deg(v) = 2m

Answer 4

La complejidad del tiempo es 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.

Answer 5

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 de la cantidad de aristas así como el número de vértices.

Answer 6

Su suma

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

puede ser reescrito 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) .

Answer 7

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

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

Entonces, el tiempo total para un ciclo simple es O (1) + O (e). Ahora sumételo para cada vértice, ya que 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)]