Dlaczego powiedzmy, że pierwsze wyszukiwanie jest przeprowadzane w czasie ?

Często stwierdza się (np. W Wikipedii ), że czas trwania pełnego wyszukiwania (BFS) na wykresie wynosi . Jednak każdy połączony wykres ma i nawet na grafie niepowiązanym BFS nigdy nie spojrzy na wierzchołek poza komponentem zawierającym wierzchołek początkowy. Ten składnik zawiera co najwyżej zbocza, więc zawiera najwyżej wierzchołków, i to są jedyne, które algorytm odwiedzi.$G=(V,E)$$O(|V|+|E|)$$|V|\leq |E|+1$$|E|$$|E|+1$

Oznacza to, że , więc dlaczego nie powiemy, że czas działania to po prostu ?$|V|+|E|\leq 2|E|+1$$O(|E|)$

_{Pojawiło się to w komentarzach do pytania o czas działania algorytmu Disjkstry .}

BFS jest zwykle opisywany w następujący sposób (z Wikipedii ).

 1  procedure BFS(G,start_v):
 2      let Q be a queue
 3      label start_v as discovered
 4      Q.enqueue(start_v)
 5      while Q is not empty
 6          v = Q.dequeue()
 7          if v is the goal:
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered:
11                 label w as discovered
12                 w.parent = v
13                 Q.enqueue(w)

Problem jest nieco subtelny: ukrywa się w linii 3! Pytanie brzmi: jakiej struktury danych będziemy używać do przechowywania, które wierzchołki zostały odkryte?

Najprostszym rozwiązaniem jest użycie tablicy boolowskiej z jednym wpisem na wierzchołek. W takim przypadku musimy zainicjować każdy element tablicy, falsea to zajmuje czas . Dotyczy to każdego wykresu, nawet jeśli nie ma żadnych krawędzi, więc nie możemy zakładać żadnego związku międzyi i otrzymujemy czas działania .$\Theta(|V|)$$|V|$$|E|$$O(|V|+|E|)$

Czy możemy uniknąć struktury danych z czasem inicjalizacji ? Naszą pierwszą próbą może być użycie połączonej listy. Jednak teraz sprawdzanie, czy wierzchołek został odkryty (linia 10), zajmuje czas liniowy w liczbie odwiedzonych wierzchołków, zamiast stałego czasu jak poprzednio. Oznacza to, że czas działania zmienia się w , co jest znacznie gorsze w najgorszym przypadku. (Zauważ, że nie chcemy przepisać tego jako ponieważ jest to jeszcze gorsze: mogłoby być tak złe jak , podczas gdy )$\Theta(|V|)$$O(|V|\,|E|)$$O(|E|^2)$$|V|^4$$|V|\,|E|\leq |V|^3$

Użycie dynamicznie zmienionej tablicy pozwoliłoby nam posortować listę, więc teraz wyszukiwanie zajmie tylko czas ale nadal daje czas działania tylko , co wciąż jest gorsze niż standardowe.$O(\log|V|)$$O(|E|\log|V|)$

Wreszcie, moglibyśmy użyć tabeli mieszającej o dynamicznym rozmiarze: zacznij od tabeli o stałym rozmiarze  i podwajaj ją za każdym razem, gdy się zapełni. Oznacza to, że ostateczny rozmiar tabeli jest co najwyżej dwa razy większy niż liczba wierzchołków wykrytych przed zakończeniem algorytmu, a to najwyżej ponieważ nigdy nie odkrywamy niczego poza składową początkowego wierzchołka. Ponadto łączna ilość pracy wykonanej przy kopiowaniu tabeli mieszającej w celu jej rozszerzenia wynosi co najwyżej. Wyszukiwanie i wstawianie do tablicy skrótów są amortyzowane przez więc faktycznie otrzymujemy czas działania .$c$$|E|+1$$c + 2c + 4c + \dots + 2|E|\leq 4|E|$ $O(1)$$O(|E|)$

Czyli jest możliwe, ale czy chciałbyś to zrobić w prawdziwej implementacji? Powiedziałbym, że prawdopodobnie nie. O ile nie masz powodu, aby sądzić, że twoje wykresy wejściowe będą miały wiele małych składników, narzut związany z utrzymaniem tabeli skrótów doda zauważalny stały czynnik do czasu działania. Zwiększenie tabeli skrótów może zająć trochę czasua wyszukiwania będą wymagały obliczenia funkcji skrótu i, średnio, spojrzenia na więcej niż jedno miejsce w tabeli. Niska wydajność pamięci podręcznej tabel skrótów może również zaszkodzić na prawdziwym komputerze. W większości przypadków ze standardową implementacją tablicy część jest dominującym terminem$O(|E|)$$4|E|$$O(|E|)$$O(|V|+|E|)$ czas działania, więc nie warto używać tabeli skrótów, aby usunąć dominujący termin, biorąc pod uwagę praktyczny koszt zrobienia tego.