Matematyka.pl

Hej, muszę obliczyć złożoność pamięciową poniższej funkcji Oszacowałem, że liczba wykonywanych kroków podczas wywołania funkcji to \(\displaystyle{ n^{\log_3{4}} }\)

Jednak czy mamy tutaj jakąkolwiek dodatkowo alokowaną pamięć poza miejscem na stosie na dodatkowe wywołania funkcji?
Czy zatem złożoność pamięciowa nie będzie równa ilości wykonywany kroków (czyli wywołań rekurencyjnych)?

Liczba kroków to asymptotycznie \(\displaystyle{ n^{\log_3 2}}\), nie \(\displaystyle{ n^{\log_3 4}}\), a złożoność pamięciowa to asymptotycznie \(\displaystyle{ \log_3 n}\).

Strukturę rekurencyjnych wywołań funkcji można zilustrować jako drzewo binarne, którego węzłami są pojedyncze wywołania. Każde takie wywołanie albo nie powoduje kolejnych (gdy n<2) i odpowiada mu liść w tym drzewie, albo powoduje dwa kolejne, i odpowiada mu węzeł wewnętrzny w drzewie, którego dwoje dzieci to te właśnie zagnieżdżone wywołania. Korzeniowi drzewa odpowiada oryginalne wywołanie.

Z tego obrazka jasno widać, że liczba kroków w algorytmie równa jest (z dokładnością do stałej) liczbie węzłów drzewa, których, jak nietrudno obliczyć, jest mniej-więcej \(\displaystyle{ 2^{\log_3 n} = n^{\log_3 2}}\). Z kolei złożoność pamięciowa to z grubsza wysokość drzewa, bo będąc w dowolnym węźle drzewa, musimy pamiętać na stosie ramki dla wszystkich "nadwywołań", a one leżą na ścieżce od obecnego węzła do korzenia. Znów nietrudno wyliczyć, że tą wysokością jest około \(\displaystyle{ \log_3 n}\) i stąd wynika powyższe szacowanie na złożoność pamięciową.