Zaczynam uczyć się złożoności czasu i zajrzałem do przykładów pod kątem złożoności czasu dla pewnego prostego rodzaju.Złożoność czasowa algorytmu wykresu głębi-pierwszego
Chciałem się dowiedzieć, jak obliczyć średnią złożoność czasu dla pierwszego wyszukiwania w głębi na wykresie z |V|=n i |E|=m, niech węzeł początkowy będzie "u", a węzłem końcowym będzie "v".
Złożoność czasowa dla DFS to O (n + m). Dostajemy tę złożoność biorąc pod uwagę fakt, że odwiedzamy każdy węzeł tylko raz i w przypadku drzewa (bez cykli) przekraczamy wszystkie krawędzie jeden raz.
Na przykład, jeśli węzłem początkowym jest u, a węzłem końcowym jest v, myślimy o najgorszym przypadku, gdy v będzie ostatnim odwiedzanym węzłem. Tak więc zaczynamy odwiedzać każdego pierwszego sąsiada połączonego komponentu, następnie komponentu połączonego z drugim sąsiadem, i tak dalej, aż do komponentu połączonego ostatniego sąsiada, gdzie znajdujemy v. Odwiedziliśmy każdy węzeł tylko raz i nie przekroczył tę samą krawędź więcej niż raz.
szanowany panie, Jestem nowy w analizie złożoności, faktycznie robię projekt na OS, staram się znaleźć cykle na wykresie alokacji zasobów ... jestem znajdowanie cykli za pomocą modyfikacji głębokości pierwszego wyszukiwania ... próbuję porównać złożoność tego algorytmu z algorytmem bankiera. Czy możesz podać matematyczne wyprowadzenie "wydajności przypadku avergae" – Learner
"Średnia wydajność przypadku" to wartość oczekiwana (czyli termin z teorii prawdopodobieństwa) czasu działania w przypadku niektórych założeń rozkładu prawdopodobieństwa nakładów. –
będzie O (n + m), jeśli wykres znajduje się w postaci listy przylegania, ale , że wykres jest w postaci matrycy przylegania to złożoność O (N * n) jak przejść przez cały rząd, aż znajdziemy przewagę.
Wiem, że jest już za późno. Ale dla innych, którzy mogą przyjść na poszukiwania, tutaj jest szczegółowa analiza. http://techieme.in/depth-first-traversal – dharam