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:Chciał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.
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.
podziwiam :)