Dlaczego złożoność czasu dla BFS/DFS to nie tylko O ​​(E) zamiast O (E + V)?

Question

Wiem, że podobne pytanie pojawia się w przepełnieniu stosu, gdzie jedna osoba zapytała, dlaczego złożoność czasowa BFS/DFS nie jest po prostu O (V).

Odpowiednią odpowiedzią było to, że E może być tak duże, jak V^2 w przypadku kompletnego wykresu, a zatem ważne jest uwzględnienie E w złożoności czasowej.

Ale jeśli V nie może być większe niż E + 1. Czy w takim przypadku brak V w złożoności czasu powinien zadziałać?

Answer 1

Jeśli jest podane, że E = kV + c dla niektórych rzeczywistych stałych k i c Następnie
O(E + V) = O(kV + c + V) = O(V) = O(E) i Twój argument jest poprawne.

Przykładem tego są drzewa.

Ogólnie rzecz biorąc jednak, E = O(V^2), a tym samym nie możemy zrobić lepiej niż O(V^2).

Dlaczego nie pisać tylko O ​​(E) zawsze?
Należy zauważyć, że mogą występować przypadki, gdy w ogóle nie ma żadnych krawędzi na wykresie (to jest O(E) ~ O(1)). Nawet w takich przypadkach będziemy musieli przejść do każdego z wierzchołków (O(V)), nie możemy zakończyć w czasie O(1).

Tak więc, tylko pisanie O(E) nie będzie generalnie robić.