Złożoność obliczeniowa algorytmu

Odpowiedz Nowy wątek
2015-01-25 21:33
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.

  • dfs.jpg (0,47 MB) - ściągnięć: 227
edytowany 2x, ostatnio: marcinek619, 2015-01-25 21:51

Pozostało 580 znaków

2015-01-26 00:54

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.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 2x, ostatnio: Shalom, 2015-01-26 01:36

Pozostało 580 znaków

2015-01-27 22:27
0

podziwiam :)

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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