Pourquoi la complexité temporelle de DFS et de BFS O( V + E )

Question

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

Je pense donc que la complexité temporelle serait :

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

où v est le sommet 1 à n

Tout d'abord, est-ce que ce que j'ai dit est correct ? Deuxièmement, comment est ce O(N + E), et l'intuition de savoir pourquoi serait vraiment gentil. Merci

Answer 1

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

Answer 2

Très simplifié sans beaucoup de formalité : chaque arête est considérée exactement deux fois, et chaque nœud est traité exactement une fois, de sorte que la complexité doit être un multiple constant du nombre d'arêtes ainsi que le nombre de sommets.

Answer 3

Une explication intuitive à cela est en analysant simplement une seule boucle :

1. visit a vertex -> O(1)
2. a pour boucle sur tous les bords incidents -> O(e) où e est un nombre de bords incidents sur un sommet donné v.

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

For every V
=> 

    O(1)
    +

    O(e)

=> O(V) + O(E)

Answer 4

La complexité temporelle est O(E+V) au lieu de O(2E+V) car si la complexité temporelle est n^2+2n+7 alors elle est écrite comme O(n^2).

Par conséquent, O(2E+V) s'écrit O(E+V)

parce que la différence entre n^2 et n importe mais pas entre n et 2n.