Pourquoi est l'heure complexité de 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é du temps serait:

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

où v est le sommet 1 à n

Premièrement, est-ce que j'ai dit-il correct? Deuxièmement, comment est-ce O(N + E), et de l'intuition pourquoi serait vraiment sympa. Grâce

InformationsquelleAutor ordinary | 2012-07-13

241

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).
- Mais tous les sommets doivent être extraites à partir de la file d'attente, et c'est log(|Q|) qu'est Ce que cette partie?
- log(|Q|) < log(N) < N d'où vous pouvez en toute sécurité ignorer le terme dans l'asymptotique
- Si dans une liste d'adjacence, chaque sommet est relié à tous les autres sommets du la complexité équivalente à O(V+E)=O(V+V^2)=O(V^2). E=V^2 parce que le plus grand nombre d'arêtes = V^2.
- Selon votre réponse, n'est ce pas la complexité O(V+2E)? Puisque chaque bord pourrait avoir un côté en commun avec un autre bord?
- Les termes constants peut être abandonné.
InformationsquelleAutor Mihai Maruseac
37

DFS(analyse):
- Paramètre/l'obtention d'un sommet/arête marque O(1) temps
- Chaque sommet est marqué deux fois
  - une fois que INEXPLORÉ
  - une fois que la visite
- Chaque bord est marqué deux fois
  - une fois que INEXPLORÉ
  - une fois que la DÉCOUVERTE ou à l'ARRIÈRE
- Méthode incidentEdges est appelée une fois pour chaque sommet
- DFS s'exécute dans O(n + m) temps fourni le graphe est représenté par la structure de liste d'adjacence
- Rappeler que Σv deg(v) = 2m
BFS(analyse):
- Paramètre/l'obtention d'un sommet/arête label prend O(1) temps
- Chaque sommet est marqué deux fois
  - une fois que INEXPLORÉ
  - une fois que la visite
- Chaque bord est marqué deux fois
  - une fois que INEXPLORÉ
  - une fois que la DÉCOUVERTE ou la CROIX
- Chaque sommet est inséré une fois dans une séquence Li
- Méthode incidentEdges est appelée une fois pour chaque sommet
- BFS s'exécute dans O(n + m) temps fourni le graphe est représenté par la structure de liste d'adjacence
- Rappeler que Σv deg(v) = 2m
- tnx pour le modifier je suis nouveau ici, donc je toujours essaie de gérer avec l'écran d'édition 🙂
- merci d'être précis en mentionnant que les graphes sont représentés par la liste d'adjacence de la structure, il était sur écoute-moi pourquoi DFS est en O(n+m), je pensais que c'était de O(n + 2m) parce que chaque arête est traversé deux fois par retours en arrière.
InformationsquelleAutor TheNewOne
18

Très simplifiée, sans trop de formalités: chaque arête est considéré exactement deux fois, et chaque noeud est traité exactement une fois, de sorte que la complexité doit être une constante multiple du nombre de bords ainsi que le nombre de sommets.

InformationsquelleAutor JavaFreak
10

Complexité temporelle est O(E+V) au lieu de O(2E+V) parce que si la complexité du temps est n^2+2n+7, il est écrit que O(n^2).

Donc O(2E+V) s'écrit O(E+V)

parce que la différence entre les n^2 et n sujets, mais pas entre n et 2n.
- quelqu'un demande ci-dessus pour le 2E en grande-oh notation....c'est pourquoi le 2 n'est pas considéré dans le temps de la complexité.
- viens de voir le post ci-dessus ma réponse....il y a le nom d'utilisateur Kehe CAI a écrit "je pense que chaque arête a été examiné à deux reprises et chaque noeud a été visité fois, de sorte que la durée totale de la complexité doit être O(2E+V)." Donc j'ai répondu acordingly....Je l'ai !!!
- J'ai enlevé mon downvote que parce que vous avez modifié votre réponse,
InformationsquelleAutor Dhruvam Gupta
3

Je pense que chaque arête a été examiné à deux reprises et chaque noeud a été visité fois, de sorte que la durée totale de la complexité doit être O(2E+V).
- Même moi, je ressens la même chose. Quelqu'un peut-il donner de plus amples explications à ce sujet ?
- Big O analyse ne tient pas compte de la constante. O(2E+V) est O(E+V).
InformationsquelleAutor Kehe CAI
2

Court mais simple explication:

J'ai le pire des cas, vous avez besoin pour visiter tous les sommets et de bord d'où
la complexité temporelle dans le pire des cas est O(V+E)

InformationsquelleAutor CodeYogi

Une explication intuitive de ce qui est simplement l'analyse d'une seule boucle:

visiter un sommet -> O(1)
une boucle sur toutes les arêtes incidentes -> O(e) où e est le nombre d'arêtes d'incident sur un même sommet v.

Donc le temps total pour une seule boucle est O(1)+O(e). Maintenant, en somme, pour chaque vertex que chaque sommet est visité une fois. Cela donne

Sigma_i

CSS:

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;
}

HTML:

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

InformationsquelleAutor Ultrablendz

Vous devez vous connecter pour publier un commentaire.