Pourquoi la complexité temporelle des deux DFS et BFS O (V + E)
L'algorithme de base pour 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
Donc je pense que la complexité temporelle serait:
v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)
Où v est le sommet 1 à n
Tout d'abord, ce que j'ai dit est-il correct? Deuxièmement, comment est-ce O(N + E), et l'intuition pourquoi serait vraiment sympa. Merci
7 réponses
Votre somme
v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)
Peut être réécrit comme
(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]
Et le premier groupe est O(N) tandis que l'autre est O(E).
DFS (analyse):
- définir/obtenir une étiquette de sommet/bord prend
O(1)Temps - chaque sommet est étiqueté deux fois
- Une fois inexploré
- Une fois visité
- chaque bord est étiqueté deux fois
- Une fois inexploré
- Une fois comme découverte ou retour
- la méthode incidentEdges est appelée une fois pour chaque sommet
- DFS s'exécute dans
O(n + m)temps à condition que le graphique soit représenté par la liste de contiguïté structure - rappelez-vous que
Σv deg(v) = 2m
BFS (analyse):
- définir/obtenir une étiquette de sommet/bord prend O (1) Temps
- chaque sommet est étiqueté deux fois
- Une fois inexploré
- Une fois visité
- chaque bord est étiqueté deux fois
- Une fois inexploré
- Une fois comme découverte ou croix
- Chaque sommet est inséré une fois dans une séquence
Li - la méthode incidentEdges est appelée une fois pour chaque vertex
- BFS s'exécute dans
O(n + m)temps à condition que le graphique soit représenté par la structure de liste d'adjacence - rappelez-vous que
Σv deg(v) = 2m
Très simplifié sans trop de formalité: chaque arête est considérée exactement deux fois, et chaque nœud est traité exactement une fois, donc la complexité doit être un multiple constant du nombre d'arêtes ainsi que du nombre de Sommets.
La complexité temporelle est O(E+V) au lieu de O(2E+V) parce que si la complexité temporelle est n^2 + 2n + 7 alors elle est écrite comme O (n^2).
Par conséquent, O (2E+V) est écrit comme O (E+V)
Parce que la différence entre N ^ 2 et n importe mais pas entre n et 2n.
Je pense que chaque arête a été considérée deux fois et que chaque nœud a été visité une fois, donc la complexité totale du temps devrait être O (2E+V).
Explication courte mais simple:
Je le pire des cas, vous auriez besoin de visiter tout le sommet et le bord par conséquent la complexité temporelle dans le pire des cas est O (V + E)
Une explication intuitive à ceci est en analysant simplement une seule boucle:
- visitez un sommet - > O (1)
- une boucle for sur tous les arêtes incidentes - > O(e) où e est un nombre d'arêtes incidentes sur un sommet donné v.
Donc le temps total pour une seule boucle est O (1)+O (e). Maintenant, additionnez-le pour chaque sommet car chaque sommet est visité une fois. Cela donne
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>Σ</span>
O(1) + O(e)
=>
<span>Σ</span>
O(1)
+
<span>Σ</span>
O(e)
=> O(V) + O(E)
</p>[ O(1) + O(e)]