Je regarde le code pour trouver la complexité de la première recherche approfondie (DFS). Comment O (| V | + | E |) diffère de O (V + E). Quelle est la signification de | · | autour de V et E? Cela signifie-t-il que la "somme de tous les sommets" est représentée par | V | ?Comment | E | diffèrent de E et | V | diffèrent de V?
| V | signifie typiquement la cardinalité (nombre d'éléments) dans V. Donc O (| V | + | E |) signifie "de l'ordre du nombre d'éléments dans V plus le nombre d'éléments dans E".
V et E sont des ensembles. Donc O (E) serait indéfini. | · | vous donne le nombre d'éléments dans l'ensemble, il est appelé cardinalité en mathématiques. Pour un graphe G = (V, E) | E | est le nombre d'arêtes, | V | est le nombre de sommets. Quand les gens écrivent O (V + E), ils signifient réellement O (| V | + | E |) et la plupart des lecteurs le comprendront, parce que c'est la seule explication plausible. Pourtant, c'est impur et je ne l'utiliserais pas moi-même.