Perché la complessità temporale di entrambi DFS e BFS O (V + E)

L’algoritmo di base per 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 

Quindi penserei che la complessità del tempo sarebbe:

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

dove v è vertice da 1 a n

In primo luogo, è quello che ho detto giusto? In secondo luogo, come è questa O(N + E) , e l’intuizione sul perché sarebbe davvero bella. Grazie

La tua sum

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

può essere riscritto come

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

e il primo gruppo è O(N) mentre l’altro è O(E) .

DFS (analisi):

  • L’impostazione / acquisizione di un’etichetta vertice / bordo richiede O(1) tempo
  • Ogni vertice è etichettato due volte
    • una volta come UNEXPLORED
    • una volta come VISITATO
  • Ogni bordo è etichettato due volte
    • una volta come UNEXPLORED
    • una volta come DISCOVERY o BACK
  • Il metodo incidentedicesges viene chiamato una volta per ogni vertice
  • DFS viene eseguito in tempo O(n + m) condizione che il grafico sia rappresentato dalla struttura dell’elenco di adiacenze
  • Ricorda che Σv deg(v) = 2m

BFS (analisi):

  • L’impostazione / acquisizione di un’etichetta vertice / bordo richiede O (1) tempo
  • Ogni vertice è etichettato due volte
    • una volta come UNEXPLORED
    • una volta come VISITATO
  • Ogni bordo è etichettato due volte
    • una volta come UNEXPLORED
    • una volta come DISCOVERY o CROSS
  • Ogni vertice viene inserito una volta in una sequenza Li
  • Il metodo incidentedicesges viene chiamato una volta per ogni vertice
  • BFS viene eseguito in tempo O(n + m) condizione che il grafico sia rappresentato dalla struttura dell’elenco di adiacenze
  • Ricorda che Σv deg(v) = 2m

Molto semplificato senza molta formalità: ogni spigolo viene considerato esattamente due volte e ogni nodo viene elaborato esattamente una volta, quindi la complessità deve essere un multiplo costante del numero di spigoli e il numero di vertici.

La complessità temporale è O(E+V) invece di O(2E+V) perché se la complessità temporale è n ^ 2 + 2n + 7 allora è scritta come O (n ^ 2).

Quindi, O (2E + V) è scritto come O (E + V)

perché la differenza tra n ^ 2 en riguarda ma non tra n e 2n.

Penso che ogni arco sia stato considerato due volte e ogni nodo è stato visitato una volta, quindi la complessità temporale totale dovrebbe essere O (2E + V).

Breve ma semplice spiegazione:

Nel caso peggiore dovresti visitare tutto il vertice e il bordo, quindi la complessità temporale nel caso peggiore è O (V + E)

Una spiegazione intuitiva è semplicemente analizzando un singolo ciclo:

  1. visita un vertice -> O (1)
  2. un ciclo for su tutti i bordi incidenti -> O (e) dove e è un numero di bordi incidente su un dato vertice v.

Quindi il tempo totale per un singolo ciclo è O (1) + O (e). Ora sumlo per ogni vertice mentre ogni vertice viene visitato una volta. Questo 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; } 
 

Σ O(1) + O(e) => Σ O(1) + Σ O(e) => O(V) + O(E)