Perché la complessità temporale per BFS/DFS non è semplicemente O (E) invece di O (E + V)?

Question

So che c'è una domanda simile nello stack overflow, dove una persona ha chiesto, perché la complessità del tempo di BFS/DFS non è semplicemente O (V).

La risposta appropriata data era che E può essere grande come V^2 in caso di grafico completo, e quindi è valido includere E in complessità temporale.

Ma, se V non può essere maggiore di E + 1. Quindi, in quel caso non avendo V nella complessità temporale, dovrebbe funzionare?

Answer 1

Se è dato che E = kV + c, per alcune costanti reali k e c poi,
O(E + V) = O(kV + c + V) = O(V) = O(E) e la tua tesi è corretta.

Un esempio di ciò sono gli alberi.

In generale, tuttavia, E = O(V^2), e quindi non possiamo fare meglio di O(V^2).

Perché non scrivere sempre solo O (E)?
Si noti che potrebbero esserci casi in cui non vi sono bordi nel grafico (ad esempio O(E) ~ O(1)). Anche in questi casi, dovremo andare a ciascuno dei vertici (O(V)), non possiamo terminare nel tempo O(1).

Pertanto, solo la scrittura O(E) non verrà eseguita in generale.