Dziękujemy wszystkim odpowiadającym za pomysły i alternatywne rozwiązania. Bardziej efektywne sposoby rozwiązywania problemów są zawsze mile widziane, jak również przypomnienia, aby zakwestionować moje założenia. Powiedział, że chciałbym, abyś na chwilę zignorował problem, który próbuję rozwiązać za pomocą algorytmu, i pomóż mi przeanalizować złożoność mojego algorytmu, tak jak to napisałem - wszystkie proste ścieżki na wykresie za pomocą wyszukiwania o ograniczonej głębokości, jak opisanotutaji wdrożonetutaj. Dzięki!

Edytuj: To jest zadanie domowe, ale już przesłałem to zadanie i chciałbym wiedzieć, czy moja odpowiedź jest poprawna. Trochę się mylę, jeśli chodzi o złożoność Big-O.

Oryginalne pytanie poniżej:

Próbuję znaleźć złożoność wyszukiwania wszystkich ścieżek podanego przezto algorytm. Biorąc pod uwagę dwa wierzchołki, znajduję wszystkie proste ścieżki między nimi, używając wyszukiwania głębokościowego.

Wiem, że złożoność czasowa DFS to O (V + E), a jej złożoność przestrzenna to O (V), a moja intuicja jest taka, że ​​złożoność przeszukiwania wszystkich ścieżek będzie czymś więcej, ale nie jestem w stanie określ, co to będzie.

Podobne pytania dotyczące SOtutaj itutaj.

Aktualizacja (w odpowiedzi na komentarz poniżej):

Próbuję rozwiązaćsześć stopni Kevina Bacona problem. Zazwyczaj wymaga to znalezienia najniższego stopnia separacji między parą aktorów, ale muszę znaleźć WSZYSTKIE stopnie separacji (na razie mniej niż 6, ale to może się zmienić).