Złożoność obliczeniowa algorytmu

0

Cześć czy mógłby mi ktoś wskazać algorytm postępowania jaki należy zastosować przy wyznaczniu złożoności obliczeniowej dla tegoż algorytmu, który jest w treści zadania:dfs.jpgChciałbym otrzymać taką odpowiedź na podstawie, której będę mógł się wzorować przy wyznaczaniu złożoności obliczeniowej innych algorytmów przedstawionych w kawałku kod.

4

Złożoność jest związana z tym przez ile węzłów w drzewie przejdziesz od korzenia do liścia, bo dokonujesz dokładnie tylu porównań i przypisań (w każdym węźle dokonujesz 1 porównania i 1 przypisania). Więc pytanie brzmi: ile węzłów mijasz na drodze od korzenia do liścia? Nie trudno zauważyć że idąc od korzenia liczba węzłów rośnie wykładniczo zgodnie z 2k. No bo najpierw ma 20=1 węzeł, potem 21=2, potem 22=4, potem 23=8 i tak dalej, a k jest numerem "poziomu" w drzewie.
Warto zauważyć pewien matematyczny trik (który powinien być oczywisty dla kazdego kto zna system binarny) że 2k -1 = 20 + 21 + ... + 2k-1
Oznacza to że drzewo z 3 poziomami ma 1+2+4 = 7 = 8-1 = 23 -1 węzłow. Czyli bardziej ogólnie drzewo z k poziomami ma 2k-1 węzłów.
Wskazówka proponuje żeby założyć że liczba węzłów drzewie wynosi n więc n = 2k-1. Nas interesuje liczba poziomów, czyli k, przedstawiona jako funkcja rozmiaru drzewa n. Robimy małe przekształcenie:
2k = n+1
k = log2(n+1)
Oczywiście złożoność interesuje nas dla wartości N dążących do nieskończoności więc nasze +1 jest zupełnie nie istotne i finalna złożoność wynosi O(log(n)).
To jest złożoność pesymistyczna, bo założyliśmy że idziemy od korzenia aż do liścia. W rzeczywistości możemy się spodziewać że potrzebujemy przejść tylko pół drzewa, ale to nie wpłynie na asymptotyczną złożoność.

Zmartwię cię: do liczenia złożonosci nie ma zbyt wielu gotowych algorytmów. Trzeba rozumieć co sie robi lub działać przez analogię do jakiegoś znanego problemu.

0

podziwiam :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1