Het basisalgoritme voor 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
Dus ik zou denken dat de tijdscomplexiteit zou zijn:
v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)
waar vhoekpunt 1tot n
is
Ten eerste, is wat ik heb gezegd juist? Ten tweede, hoe is dit O(N + E), en intuïtie over het waarom zou heel fijn zijn. Bedankt
Antwoord 1, autoriteit 100%
Uw bedrag
v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)
kan worden herschreven als
(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]
en de eerste groep is O(N)terwijl de andere O(E)is.
Antwoord 2, autoriteit 15%
DFS(analyse):
- Het instellen/krijgen van een hoekpunt/randlabel kost
O(1)tijd - Elk hoekpunt is twee keer gelabeld
- eens als ONVERKLAARD
- eenmaal als BEZOCHT
- Elke rand is twee keer gelabeld
- eens als ONVERKLAARD
- eenmaal als ONTDEKKING of TERUG
- Methode incidentEdges wordt één keer aangeroepen voor elk hoekpunt
- DFS wordt uitgevoerd in
O(n + m)tijd op voorwaarde dat de grafiek wordt weergegeven door de aangrenzend lijststructuur - Onthoud dat
Σv deg(v) = 2m
BFS(analyse):
- Het instellen/krijgen van een hoekpunt/randlabel kost O(1) tijd
- Elk hoekpunt is twee keer gelabeld
- eens als ONVERKLAARD
- eenmaal als BEZOCHT
- Elke rand is twee keer gelabeld
- eens als ONVERKLAARD
- eenmaal als DISCOVERY of CROSS
- Elk hoekpunt wordt één keer ingevoegd in een reeks
Li - Methode incidentEdges wordt één keer aangeroepen voor elk hoekpunt
- BFS wordt uitgevoerd in
O(n + m)tijd op voorwaarde dat de grafiek wordt weergegeven door de lijststructuur van de aangrenzende lijst - Onthoud dat
Σv deg(v) = 2m
Antwoord 3, autoriteit 9%
Zeer vereenvoudigd zonder veel formaliteit: elke rand wordt precies twee keer beschouwd en elke knoop wordt precies één keer verwerkt, dus de complexiteit moet een constant veelvoud zijn van het aantal randen en het aantal hoekpunten.
Antwoord 4, autoriteit 4%
Tijdcomplexiteit is O(E+V)in plaats van O(2E+V)want als de tijdcomplexiteit n^2+2n+7 is, dan is dat ook zo geschreven als O(n^2).
Daarom wordt O(2E+V) geschreven als O(E+V)
omdat het verschil tussen n^2 en n van belang is, maar niet tussen n en 2n.
Antwoord 5, autoriteit 3%
Een intuïtieve verklaring hiervoor is door simpelweg een enkele lus te analyseren:
- bezoek een hoekpunt -> O(1)
- een for-lus op alle invallende randen -> O(e) waarbij e een aantal randen is die op een bepaald hoekpunt vallen v.
Dus de totale tijd voor een enkele lus is O(1)+O(e). Tel het nu op voor elk hoekpunt, aangezien elk hoekpunt één keer wordt bezocht. Dit geeft
For every V
=>
O(1)
+
O(e)
=> O(V) + O(E)
Antwoord 6, autoriteit 2%
Ik denk dat elke rand twee keer is overwogen en elk knooppunt één keer is bezocht, dus de totale tijdcomplexiteit zou O(2E+V) moeten zijn.
Antwoord 7
Korte maar eenvoudige uitleg:
In het ergste geval zou je dus alle hoekpunten en randen moeten bezoeken
de tijdscomplexiteit in het ergste geval is O(V+E)
Antwoord 8
Het is O(V+E) omdat elk bezoek aan v van V elke e van E moet bezoeken waar |e| <= V-1. Aangezien er V-bezoeken zijn aan v van V, dan is dat O(V). Nu moet je V * |e| . toevoegen = E => O(E). De totale tijdcomplexiteit is dus O(V + E).